#include <cstdio> //#include <cassert> //#define BUF (1024*812) #define BUF 833334 #define C0 (1) #define C1 (C0*26) #define C2 (C1*26) #define C3 (C2*26) #define C4 (C3*26) #define C5 (C4*26) #define C6 (C5*26) #define NLIM (20000000) #define Q 1845589297LL #define D C1 typedef unsigned ui; #define CHBUF(ind,pos,elem) bufc[ind] = ((bufc[ind] / c[pos+1] ) * c[pos+1] + c[pos] * (elem) + bufc[ind] % c[pos] ) #define RAWBUF(ind,pos) ((bufc[ind] / c[pos]) % C1 ) #define RECALC(rpos) ((kon+(BUF*6)-(l-(rpos)))%(BUF*6)) #define GETBUF(rpos) (char)(((rpos)<l && (rpos+1)+(BUF*6)>l)?RAWBUF(RECALC(rpos)/6,RECALC(rpos)%6):100) //char GETBUF(ui rpos){ // return (((rpos)<l && (rpos+1)+(BUF*6)>l)?RAWBUF(RECALC(rpos)/6,RECALC(rpos)%6):100); //} int main(){ const int c[7] = {C0,C1,C2,C3,C4,C5,C6}; char a,adc=0;//wczytywana ui n,k=0;//liczba wczytanych ui bufc[BUF] = { 0 }, poc=0, kon=0, l=0; unsigned long long lewy, prawy, H = 1; const char tnie[] = "NIE"; scanf(" %d",&n); while(scanf(" %c",&a) != 0){ if(a > 'z' || a < 'a'){ break; } a-='a'; adc ^= a; if(k<NLIM/2){//TODO:sprawdzic warunek CHBUF(kon/6,kon%6,a); kon++; kon = kon % (6*BUF); l++; } //RabinKarp rolling hash if(k==0){ lewy = a; prawy = a; }else{ //fprintf(stderr,"PROC: k=%d a=%c ",k,char(a)+'a'); if(k%2 == 0){ H *= D; H = H % Q; //fprintf(stderr," lewy +=%c prawy+=%c",GETBUF(k/2)+'a',char(a)+'a'); lewy = (lewy + H*GETBUF(k/2)) % Q; prawy = (D*prawy + a) % Q; }else{ //fprintf(stderr,"prawy +=%c prawy-=%c",char(a)+'a',GETBUF(k/2)+'a'); prawy = D*(Q*D + prawy - H*GETBUF(k/2)) % Q + a; prawy %= Q; } //fprintf(stderr,"\t%llu %llu H= %llu\n",lewy,prawy,H); } k++; } if(prawy == lewy){ if(k%2 == 0){ if(adc!=0){ puts(tnie); return 0; } }else{ if(adc!=GETBUF(k/2)){ puts(tnie); return 0; } } for(int i=0;i<k/2;i++){ char c1 = GETBUF(i); char c2 = GETBUF(k-i-1); if(c1 != 100 && c2 != 100 && c2 != c1){ puts(tnie); return 0; } } puts("TAK"); }else{ puts(tnie); } //for(int i=0;i<k;i++){ // printf("%c", (char)GETBUF(i)+'a'); //} }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <cstdio> //#include <cassert> //#define BUF (1024*812) #define BUF 833334 #define C0 (1) #define C1 (C0*26) #define C2 (C1*26) #define C3 (C2*26) #define C4 (C3*26) #define C5 (C4*26) #define C6 (C5*26) #define NLIM (20000000) #define Q 1845589297LL #define D C1 typedef unsigned ui; #define CHBUF(ind,pos,elem) bufc[ind] = ((bufc[ind] / c[pos+1] ) * c[pos+1] + c[pos] * (elem) + bufc[ind] % c[pos] ) #define RAWBUF(ind,pos) ((bufc[ind] / c[pos]) % C1 ) #define RECALC(rpos) ((kon+(BUF*6)-(l-(rpos)))%(BUF*6)) #define GETBUF(rpos) (char)(((rpos)<l && (rpos+1)+(BUF*6)>l)?RAWBUF(RECALC(rpos)/6,RECALC(rpos)%6):100) //char GETBUF(ui rpos){ // return (((rpos)<l && (rpos+1)+(BUF*6)>l)?RAWBUF(RECALC(rpos)/6,RECALC(rpos)%6):100); //} int main(){ const int c[7] = {C0,C1,C2,C3,C4,C5,C6}; char a,adc=0;//wczytywana ui n,k=0;//liczba wczytanych ui bufc[BUF] = { 0 }, poc=0, kon=0, l=0; unsigned long long lewy, prawy, H = 1; const char tnie[] = "NIE"; scanf(" %d",&n); while(scanf(" %c",&a) != 0){ if(a > 'z' || a < 'a'){ break; } a-='a'; adc ^= a; if(k<NLIM/2){//TODO:sprawdzic warunek CHBUF(kon/6,kon%6,a); kon++; kon = kon % (6*BUF); l++; } //RabinKarp rolling hash if(k==0){ lewy = a; prawy = a; }else{ //fprintf(stderr,"PROC: k=%d a=%c ",k,char(a)+'a'); if(k%2 == 0){ H *= D; H = H % Q; //fprintf(stderr," lewy +=%c prawy+=%c",GETBUF(k/2)+'a',char(a)+'a'); lewy = (lewy + H*GETBUF(k/2)) % Q; prawy = (D*prawy + a) % Q; }else{ //fprintf(stderr,"prawy +=%c prawy-=%c",char(a)+'a',GETBUF(k/2)+'a'); prawy = D*(Q*D + prawy - H*GETBUF(k/2)) % Q + a; prawy %= Q; } //fprintf(stderr,"\t%llu %llu H= %llu\n",lewy,prawy,H); } k++; } if(prawy == lewy){ if(k%2 == 0){ if(adc!=0){ puts(tnie); return 0; } }else{ if(adc!=GETBUF(k/2)){ puts(tnie); return 0; } } for(int i=0;i<k/2;i++){ char c1 = GETBUF(i); char c2 = GETBUF(k-i-1); if(c1 != 100 && c2 != 100 && c2 != c1){ puts(tnie); return 0; } } puts("TAK"); }else{ puts(tnie); } //for(int i=0;i<k;i++){ // printf("%c", (char)GETBUF(i)+'a'); //} } |