Submission #25891

#	Time	Username	Problem	Language	Result	Execution time	Memory
25891		model_code	Walk (POI13_spa)	C++11	100 / 100	4143 ms	126116 KiB

spa

/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Spacer                                        *
 *   Autor:                Wiktor Kuropatwa                              *
 *   Zlozonosc czasowa:    O(n^2 * k)                                    *
 *   Zlozonosc pamieciowa: O(nk)                                         *
 *   Opis:                 Rozwiazanie wzorcowe                          *
 *                                                                       *
 *************************************************************************/

#include <cstdio>

const int HSIZE = 5000011;
const int EMPTY = 0;
const int MAXK = 500009;

long long forbidden[MAXK];
int fprev[MAXK];
int fhash[MAXK];
long long visited[HSIZE];
int vprev[HSIZE];
int vhash[HSIZE];
int vfree = 1, ffree = 1;
long long q[HSIZE];

inline void hashSetInsert(long long* set, int* prev, int* hash, int &free, long long value, int size)
{
    set[free] = value;
    prev[free] = hash[value%size];
    hash[value%size] = free++;
}

inline bool hashSetLookup(long long* set, int* prev, int* hash, long long value, int size)
{
    for(int t = hash[value%size]; t>0; t=prev[t])
        if(set[t] == value) return true;
    return false;
}

inline void hashSetClear(int* hash, int &free, int size)
{
    free = 1;
    for(int i = 0; i<size; i++)
        hash[i] = 0;
}

int n,k;

bool graphSearch(long long s, long long t, int bound)
{
    int b = 0, e = 0;
    int c = 1;
    q[e++] = s;
    hashSetInsert(visited,vprev,vhash,vfree,s,HSIZE);
    while(b < e && c < bound)
    {
        long long v = q[b++];
        for(int i = 0; i<n; i++)
        {
            long long next = v ^ (1LL << i);
            if(next == t) return true;
            if(!hashSetLookup(forbidden,fprev,fhash,next,MAXK) && !hashSetLookup(visited,vprev,vhash,next,HSIZE))
            {
                q[e++] = next;
                hashSetInsert(visited,vprev,vhash,vfree,next,HSIZE);
                c++;
            }
        }
    }
    if(c >= bound) return true;
    return false;
}

bool solve(long long s, long long t)
{
    int bound = n*k + 1;
    bool a = graphSearch(s,t,bound);
    hashSetClear(vhash,vfree,HSIZE);
    bool b = graphSearch(t,s,bound);
    return a && b;
}

long long x,y;

long long readBinary()
{
    char buf[100];
    scanf("%s", buf);
    long long r = 0;
    for(int i = n-1; i>=0; i--)
        if(buf[i] == '1')
            r += (1LL<<(n-i-1));
    return r;
}
void read()
{
    scanf("%d %d", &n, &k);
    x = readBinary();
    y = readBinary();
    for(int i = 0; i<k; i++)
    {
        long long a;
        a = readBinary();
        hashSetInsert(forbidden,fprev,fhash,ffree,a,MAXK);
    }
}

int main()
{
    read();
    if(solve(x,y))
        printf("TAK\n");
    else
        printf("NIE\n");
}

Compilation message (stderr)

spa.cpp: In function 'long long int readBinary()':
spa.cpp:90:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", buf);
                     ^
spa.cpp: In function 'void read()':
spa.cpp:99:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
                           ^

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13