0
Your rating: None

CodeChef submission 79964 (C++ 4.0.0-8)

CodeChef submission 79964 (C++ 4.0.0-8) plaintext list. Status: AC, problem NSUDOKU, contest AUGMINI. By triplem (Stephen Merriman), 2009-08-24 14:58:34.
  1. #include <iostream>
  2. #include <cstdlib>
  3. using namespace std;
  4. int grid[900][900];
  5. bool preset[900][900];
  6. int cc[3][900][900];
  7. int L,N;
  8. int numstates;
  9. char output[50000000];
  10. char  input[50000000];
  11. long long sizeatend;
  12. int starttime;
  13. int outpos=0, inpos=0, numcharsin;
  14. void writeint(int a) {
  15.     if (a==0) {
  16.         output[outpos++]='0';
  17.         return;
  18.     }
  19.     char tmp[10];
  20.     int tp = 0;
  21.     while (a) {tmp[tp++]=a%10;a/=10;}
  22.     while (tp--) {
  23.         output[outpos++]=tmp[tp]+'0';
  24.     }
  25. }
  26. int getint() {
  27.     while (input[inpos]<'0' || input[inpos]>'9') inpos++;
  28.     int ret = 0;
  29.     while (inpos<numcharsin && input[inpos]>='0' && input[inpos]<='9') ret = 10*ret+input[inpos++]-'0';
  30.     return ret;
  31. }
  32. typedef struct State {
  33.     long long parts[15];
  34.     State() {for (int i=0; i<15; i++) parts[i]=0;}
  35.     void update(int val) {
  36. //        printf("before: %I64d\n",parts[val/61]);
  37. //        printf("Adding 1LL<<%d\n",val);
  38.         parts[val/61]|=1LL<<(val%61);
  39. //        printf("after: %I64d\n",parts[val/61]);
  40.     }
  41.     void reset() {
  42.         for (int i=0; i<15; i++) parts[i]=0;
  43.     }
  44.     void print() {
  45.         for (int i=0; i<numstates; i++)
  46.         for (int j=0; j<61; j++) printf("%d",(parts[i]&(1LL<<j))?1:0);
  47.         printf("\n");
  48.     }
  49. };
  50. int getscore() {
  51.     int score = 0;
  52.     static bool found[3][900][900];
  53.     memset(found,0,3*900*900*sizeof(bool));
  54.     for (int i=0; i<L; i++)
  55.     for (int j=0; j<L; j++) {
  56.         found[0][i][grid[i][j]-1]=true;
  57.         found[1][j][grid[i][j]-1]=true;
  58.         found[2][(i/N)*N+(j/N)][grid[i][j]-1]=true;
  59.     }
  60.     for (int i=0; i<L; i++)
  61.     for (int k=0; k<L; k++)
  62.     for (int j=0; j<3; j++) if (!found[j][i][k]) score++;
  63. return score;
  64.  
  65. }
  66. State states[3][900];
  67. void update(int x, int y) {
  68.     cc[0][x][grid[x][y]-1]++;
  69.     states[0][x].update(grid[x][y]-1);
  70.     cc[1][y][grid[x][y]-1]++;    
  71.     states[1][y].update(grid[x][y]-1);
  72.     cc[2][N*(x/N)+y/N][grid[x][y]-1]++;    
  73.     states[2][N*(x/N)+y/N].update(grid[x][y]-1);
  74. }
  75. int getbest(int x, int y, int type) {
  76. //    printf("At %d,%d\n",x,y);
  77.     State *one = &states[0][x];
  78.     State *two = &states[1][y];
  79.     State *three = &states[2][N*(x/N)+y/N];
  80.     long long stophere = (1LL<<61)-1;
  81.     
  82.     for (int i=0; i<numstates; i++) {
  83.         long long stop = (i==numstates-1?sizeatend:stophere);        
  84.         long long tmp = one->parts[i]|two->parts[i]|three->parts[i];
  85.         if (tmp==stop) continue;
  86.         for (int j=0; j<61 && 61*i+j<L; j++) {
  87.             if (tmp&1) {tmp/=2;continue;}
  88.             return 61*i+j+1;
  89.             tmp/=2;
  90.         }
  91.     }
  92.     for (int i=0; i<numstates; i++) {
  93.         long long stop = (i==numstates-1?sizeatend:stophere);
  94.         long long tmp1 = one->parts[i]|two->parts[i];
  95.         long long tmp2 = one->parts[i]|three->parts[i];
  96.         long long tmp3 = two->parts[i]|three->parts[i];                
  97.         if (tmp1==stop && tmp2==stop && tmp3==stop) continue;
  98.         long long tmp;
  99.         if (tmp1!=stop) tmp=tmp1;
  100.         else if (tmp2!=stop) tmp=tmp2;
  101.         else tmp = tmp3;
  102.         for (int j=0; j<61 && 61*i+j<L; j++) {
  103.             if (tmp&1) {tmp/=2;continue;}
  104.             return 61*i+j+1;
  105.             tmp/=2;
  106.         }
  107.     }
  108.     if (type==100) {
  109.         for (int i=0; i<numstates; i++) {
  110.             long long stop = (i==numstates-1?sizeatend:stophere);            
  111.             long long tmp1 = one->parts[i];
  112.             long long tmp2 = two->parts[i];
  113.             long long tmp3 = three->parts[i];
  114.             if (tmp1==stop && tmp2==stop && tmp3==stop) continue;
  115.             long long tmp;
  116.             if (tmp1!=stop) tmp=tmp1;
  117.             else if (tmp2!=stop) tmp=tmp2;
  118.             else tmp = tmp3;
  119.             for (int j=0; j<61 && 61*i+j<L; j++) {
  120.                 if (tmp&1) {tmp/=2;continue;}
  121.                 return 61*i+j+1;
  122.                 tmp/=2;
  123.             }
  124.         }  
  125.         //fprintf(stderr,"\n\n\n\n\n\n");
  126.         return rand()%L+1;
  127.     }
  128.     return 0;
  129. }
  130. int perm[810000];
  131. void print() {
  132.     for (int i=0; i<L; i++) {
  133.         for (int j=0; j<L; j++) {
  134.             printf("%d ",grid[i][j]);
  135.         }
  136.         printf("\n");
  137.     }
  138.     printf("\n");    
  139. }
  140. int getdelta(int x, int y1, int y2, bool doit) {
  141.     if (grid[x][y1]==grid[x][y2]) return 0;
  142.     // suppose we switch (x,y1) and (x,y2)
  143.     int delta = 0;
  144.     // row x is unchanged
  145.     // column y1
  146.     // we increase the grid[x][y2] count, decrease the grid[x][y1] coun
  147.     if (cc[1][y1][grid[x][y2]-1]==0) {delta++; if (doit) cc[1][y1][grid[x][y2]-1]++; }
  148.     if (cc[1][y1][grid[x][y1]-1]==1) {delta--; if (doit) cc[1][y1][grid[x][y1]-1]--; }
  149.     // column y2
  150.     if (cc[1][y2][grid[x][y2]-1]==1) {delta--; if (doit) cc[1][y2][grid[x][y2]-1]--; }
  151.     if (cc[1][y2][grid[x][y1]-1]==0) {delta++; if (doit) cc[1][y2][grid[x][y1]-1]++; }
  152.     if (y1/N!=y2/N) {
  153.         if (cc[2][N*(x/N)+y1/N][grid[x][y2]-1]==0) {delta++;if (doit) cc[2][N*(x/N)+y1/N][grid[x][y2]-1]++; }
  154.         if (cc[2][N*(x/N)+y1/N][grid[x][y1]-1]==1) {delta--;if (doit) cc[2][N*(x/N)+y1/N][grid[x][y1]-1]--; }
  155.         
  156.         if (cc[2][N*(x/N)+y2/N][grid[x][y2]-1]==1) {delta--;if (doit) cc[2][N*(x/N)+y2/N][grid[x][y2]-1]--; }
  157.         if (cc[2][N*(x/N)+y2/N][grid[x][y1]-1]==0) {delta++;if (doit) cc[2][N*(x/N)+y2/N][grid[x][y1]-1]++; }
  158.     }
  159.     if (doit) {int tmp = grid[x][y1]; grid[x][y1] = grid[x][y2]; grid[x][y2] = tmp; }
  160.     return delta;
  161. }
  162. int getdelta2(int x, int y1, int y2, bool doit) {
  163.     if (grid[y1][x]==grid[y2][x]) return 0;
  164.     // suppose we switch (x,y1) and (x,y2)
  165.     int delta = 0;
  166.     // row x is unchanged
  167.     // column y1
  168.     // we increase the grid[y2][x] count, decrease the grid[y1][x] coun
  169.     if (cc[0][y1][grid[y2][x]-1]==0) {delta++; if (doit) cc[0][y1][grid[y2][x]-1]++; }
  170.     if (cc[0][y1][grid[y1][x]-1]==1) {delta--; if (doit) cc[0][y1][grid[y1][x]-1]--; }
  171.     // column y2
  172.     if (cc[0][y2][grid[y2][x]-1]==1) {delta--; if (doit) cc[1][y2][grid[y2][x]-1]--; }
  173.     if (cc[0][y2][grid[y1][x]-1]==0) {delta++; if (doit) cc[1][y2][grid[y1][x]-1]++; }
  174.     if (y1/N!=y2/N) {
  175.         if (cc[2][N*(x/N)+y1/N][grid[y2][x]-1]==0) {delta++;if (doit) cc[2][N*(x/N)+y1/N][grid[y2][x]-1]++; }
  176.         if (cc[2][N*(x/N)+y1/N][grid[y1][x]-1]==1) {delta--;if (doit) cc[2][N*(x/N)+y1/N][grid[y1][x]-1]--; }
  177.         
  178.         if (cc[2][N*(x/N)+y2/N][grid[y2][x]-1]==1) {delta--;if (doit) cc[2][N*(x/N)+y2/N][grid[y2][x]-1]--; }
  179.         if (cc[2][N*(x/N)+y2/N][grid[y1][x]-1]==0) {delta++;if (doit) cc[2][N*(x/N)+y2/N][grid[y1][x]-1]++; }
  180.     }
  181.     if (doit) {int tmp = grid[y1][x]; grid[y1][x] = grid[y2][x]; grid[y2][x] = tmp; }
  182.     return delta;
  183. }
  184. int score;
  185. void doswitch(int x, int y, int z) {
  186.     int delta = getdelta(x,y,z,false);
  187.     if (delta>0) {
  188.         getdelta(x,y,z,true);
  189.         #ifndef ONLINE_JUDGE
  190.         fprintf(stderr,"%d\n",score);
  191.         score -= delta;
  192.         #endif
  193.     }
  194. }
  195. void doswitch2(int x, int y, int z) {
  196.     int delta = getdelta2(x,y,z,false);
  197.     if (delta>0) {
  198.         getdelta2(x,y,z,true);
  199.         #ifndef ONLINE_JUDGE
  200.         fprintf(stderr,"%d\n",score);
  201.         score -= delta;
  202.         #endif
  203.     }
  204.  
  205. }
  206. int randperm2[900];
  207.  
  208. void checkbrute() {
  209.  
  210.     #ifndef ONLINE_JUDGE
  211.     score = getscore();
  212.     fprintf(stderr,"Starting at %d\n",score);
  213.     #endif
  214.     
  215.     while (true) {
  216.         int xx;
  217.  
  218.     for (xx=0; xx<L && (clock()-starttime)*1./CLOCKS_PER_SEC<2.7; xx++) {
  219.         int x = randperm2[xx];
  220.         for (int y1=0; y1<L; y1++) { if (preset[x][y1]) continue;
  221.         for (int y2=y1+1; y2<L && y1/N==y2/N; y2++) { if (preset[x][y2]) continue;
  222.             doswitch(x,y1,y2);
  223.         }}
  224.         if ((clock()-starttime)*1./CLOCKS_PER_SEC>=2.7) break;
  225.         for (int y1=0; y1<L; y1++) { if (preset[y1][x]) continue;
  226.         for (int y2=y1+1; y2<L && y1/N==y2/N; y2++) { if (preset[y2][x]) continue;
  227.             doswitch2(x,y1,y2);        
  228.         }}        
  229.     }
  230.     if (xx!=L) break;
  231.     }
  232.     
  233. }
  234. int main() {
  235.     starttime = clock();
  236.     cin.read(input,50000000);
  237.     numcharsin = cin.gcount();    
  238.     N = getint(); int K = getint();
  239.     L = N*N;
  240.     for (int i=0; i<L; i++) randperm2[i]=i;
  241.     random_shuffle(randperm2,randperm2+L);
  242.     int LL = L*L;
  243.     srand(time(NULL));
  244.     for (int i=0; i<LL; i++) perm[i]=i;
  245.     random_shuffle(perm,perm+LL);
  246. /*    for (int i=0; i<LL; i++) {
  247.         int m = i/L;
  248.         int n = i%L;
  249.         int x = m/N;
  250.         int y = m%N;
  251.         x += N*(n/N);
  252.         y += N*(n%N);
  253.         perm[i] = x*L+y;
  254.     }
  255.   */ 
  256.     numstates = (L+60)/61;
  257.     int leftover = L%61;
  258.  
  259.     sizeatend = (1LL<<leftover)-1;
  260. //    printf("numstates: %d\n",numstates);
  261.     for (int i=0; i<K; i++) {
  262.         int x = getint();
  263.         int y = getint();
  264.         int d = getint();x--;-y--;
  265.         grid[x][y]=d;
  266.         preset[x][y]=true;
  267.         update(x,y);
  268.     }
  269.     for (int i=0; i<LL; i++) {
  270.         int x = perm[i]%L;
  271.         int y = perm[i]/L;
  272.         if (grid[x][y]==0) {
  273.             grid[x][y]=getbest(x,y,0);
  274.             if (grid[x][y]) update(x,y);
  275.         }
  276.     }
  277.     for (int i=0; i<L; i++)
  278.     for (int j=0; j<L; j++) {
  279.         if (grid[i][j]==0) {
  280.             grid[i][j]=getbest(i,j,100);
  281.             update(i,j);
  282.         }
  283.     }
  284.     checkbrute();
  285. #ifndef ONLINE_JUDGE
  286. {
  287. fprintf(stderr,"Score: %d\n",getscore());
  288. }
  289. #endif
  290.     for (int i=0; i<L; i++) {
  291.         for (int j=0; j<L; j++) {
  292.             writeint(grid[i][j]);
  293.             output[outpos++]=' ';
  294.         }
  295.         output[outpos++]='\n';
  296.     }
  297.     cout.write(output,outpos);
  298. }
  299.

Comments