FAU WinterContest 2012

C-naive.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;
#define REP(i, a, b)    for(int i=int(a); i<int(b); i++)
typedef long long       ll;

const int MAXS=10001, MAXQ=100001, MAXM=100001;
int t, S, Q, query;

pair<ll,int> materials[2*(MAXM-1)+1];
pair<ll,int> new_materials[MAXM];

//ll L[MAXS], U[MAXS], I[MAXS];
ll L,U,I;

template < typename P1, typename P2 >
struct less_first
{
    typedef pair<P1,P2> value_type;
    bool operator()( const value_type& lhs, const value_type& rhs )
    {
        return lhs.first < rhs.first;
    }
    bool operator()( const value_type& lhs, const ll& rhs )
    {
        return lhs.first < rhs;
    }
};

int main()
{
    scanf("%d\n", &t);
    REP(cc,0,t)
    {
        scanf("%d %d\n", &S, &Q);
        /*memset(L, 0LL, MAXS);
        memset(U, 0LL, MAXS);
        memset(I, 0LL, MAXS);*/

        int next_slot = 0;
        memset(materials, 0, 2*(MAXM-1)+1);
        REP(i,0,S)
        {
            //scanf("%lld %lld %lld\n", &L[i], &U[i], &I[i]);
            scanf("%lld %lld %lld\n", &L,&U,&I);

            // generate min(100k, U) terms of the sequence
            int last_slot = MAXM;
            memset(new_materials, 0, MAXM);
            REP(j,0,MAXM)
            {
                //if (L[i] > U[i])
                if (L > U)
                {
                    last_slot = j;
                    break;
                }
                //new_materials[j] = make_pair(height, i+1);
                new_materials[j] = make_pair(L, i+1);
                //L[i] += I[i];
                L += I;
            }

            // merge sort both arrays
            REP(j,0,last_slot)
            {
                materials[next_slot+j] = new_materials[j];
            }

            next_slot = min(MAXM, next_slot+last_slot);
            if (next_slot >= MAXM)
            {
                sort(materials, materials+next_slot+last_slot, less_first<ll,int>());
            }
        }

        REP(i,0,Q)
        {
            scanf("%d", &query);
            // (height, type)
            printf("%lld %d\n",
                   materials[query-1].first, materials[query-1].second);
            /*
            printf("(%d,%d): %lld %d\n", cc, i,
                   materials[query-1].first, materials[query-1].second);
             */
        }
    }
    return 0;
}

I-naive.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;
#define REP(i, a, b)    for(int i=int(a); i<int(b); i++)
typedef long long       ll;

const int MAXN = 100000, MAXS = 20;
int t, n, m;
char dict[MAXN][MAXS];

int main()
{
    //scanf("%d\n", &t);
    //REP(cc,0,t)
    //{
        scanf("%d %d\n", &n, &m);
        memset(dict, 0, MAXN * MAXS);
        REP(i,0,n)
        {
            scanf("%s\n", dict[i]);
            //printf("read in: %d - %s\n", i, dict[i]);
        }

        REP(i,0,m)
        {
            char word[MAXS+1];
            memset(word, 0, MAXS+1);
            string line;
            getline(cin, line);
            REP(j,0,line.length())
            {
                word[j] = line[j];
            }
            word[line.length()] = '\0';
            /*scanf("%[^\n]\n",&word);
            REP(j,0,MAXS)
            {
                if (word[j] == ' ')
                    printf("_");
                else
                    printf("%c", word[j]);
            }
            printf("\n");*/

            char answer[MAXS+1];
            memset(answer, 0, MAXS+1);
            int found = 0;
            REP(j,0,n)
            {
                // for each word in dict
                if (line.length() != strlen(dict[j]))
                    continue;   // next word in dict
                if (found > 1)
                    break;

                REP(k,0,MAXS+1)
                {
                    if (word[k] != ' ' && word[k] != dict[j][k])
                    {
                        break;
                    }
                    else if (word[k] == '\0')
                    {
                        // copy first occurrence
                        if (found == 0)
                        {
                            strcpy(answer, dict[j]);
                        }
                        found++;
                        break;
                    }
                }
            }

            if (found == 0)
            {
                printf("not found\n");
                //printf("%d: not found\n", i);
            }
            else if (found == 1)
            {
                printf("%s\n", answer);
                //printf("%d: %s\n", i, answer);
            }
            else
            {
                printf("not unique\n");
                //printf("%d: not unique\n", i);
            }   
        }
    //}
    return 0;
}