fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define WAS_SEEN(x) ( (seen[(x)>>5] >> ((x)&31)) & 1 )
  5. #define MARK_SEEN(x) seen[(x)>>5] |= 1u << ((x)&31)
  6.  
  7. unsigned oned[1<<16];       // log2 of one-dimensional SG values
  8. unsigned seen[(1<<27)+1];   // which SG values were already seen in this pass?
  9. unsigned dp[2][1<<16];      // dp[x mod 2][y] = xor of rectangle (x,y)--(rr,cc)
  10. unsigned precomputed[17][17];
  11.  
  12. int main() {
  13.     for (int i=0; i<(1<<16); ++i) { 
  14.         oned[i] = 0; 
  15.         while ((i+1) % (1 << (oned[i]+1)) == 0) oned[i] += 1; 
  16.     }
  17.     for (int r=0; r<=16; ++r) for (int c=r; c<=16; ++c) { 
  18.         int rr=(1<<r)-1, cc=(1<<c)-1;
  19.         cout << "computing SG(" << rr << "," << cc << ")" << endl;
  20.         memset(seen,0,sizeof(seen));
  21.         memset(dp,0,sizeof(dp));
  22.  
  23.         MARK_SEEN(0); // toggling just the single cell
  24.         for (int y=cc-1; y>=0; --y) { 
  25.             dp[rr&1][y] = dp[rr&1][y+1] ^ precomputed[ oned[rr] ][ oned[y] ]; 
  26.             MARK_SEEN( dp[rr&1][y] );
  27.         }
  28.         for (int x=rr-1; x>=0; --x) {
  29.             int cur=x&1, prev=1-cur;
  30.             dp[cur][cc] = dp[prev][cc] ^ precomputed[ oned[x] ][ oned[cc] ];
  31.             MARK_SEEN( dp[cur][cc] );
  32.             for (int y=cc-1; y>=0; --y) {
  33.                 dp[cur][y] = dp[cur][y+1] ^ dp[prev][y] ^ dp[prev][y+1] 
  34.                              ^ precomputed[ oned[x] ][ oned[y] ];
  35.                 MARK_SEEN( dp[cur][y] );
  36.             }
  37.         }
  38.         precomputed[r][c] = 0;
  39.         while (WAS_SEEN(precomputed[r][c])) ++precomputed[r][c];
  40.         precomputed[c][r] = precomputed[r][c];
  41.         cout << precomputed[r][c] << endl; 
  42.     }
  43. }
Time limit exceeded #stdin #stdout 5s 540160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
computing SG(0,0)
1
computing SG(0,1)
2
computing SG(0,3)
4
computing SG(0,7)
8
computing SG(0,15)
16
computing SG(0,31)
32
computing SG(0,63)
64
computing SG(0,127)
128
computing SG(0,255)
256
computing SG(0,511)
512
computing SG(0,1023)
1024
computing SG(0,2047)
2048
computing SG(0,4095)
4096
computing SG(0,8191)
8192
computing SG(0,16383)
16384
computing SG(0,32767)
32768
computing SG(0,65535)
65536
computing SG(1,1)
3
computing SG(1,3)
8
computing SG(1,7)
12
computing SG(1,15)
32
computing SG(1,31)
48
computing SG(1,63)
128
computing SG(1,127)
192
computing SG(1,255)
512
computing SG(1,511)
768
computing SG(1,1023)
2048
computing SG(1,2047)
3072
computing SG(1,4095)
8192
computing SG(1,8191)
12288
computing SG(1,16383)
32768
computing SG(1,32767)
49152
computing SG(1,65535)
131072
computing SG(3,3)
6
computing SG(3,7)
11
computing SG(3,15)
64
computing SG(3,31)
128
computing SG(3,63)
96
computing SG(3,127)
176
computing SG(3,255)
1024
computing SG(3,511)
2048
computing SG(3,1023)
1536
computing SG(3,2047)
2816
computing SG(3,4095)
16384
computing SG(3,8191)
32768
computing SG(3,16383)
24576
computing SG(3,32767)
45056
computing SG(3,65535)
262144
computing SG(7,7)
13
computing SG(7,15)
128
computing SG(7,31)
192
computing SG(7,63)
176
computing SG(7,127)
208
computing SG(7,255)
2048
computing SG(7,511)
3072
computing SG(7,1023)
2816
computing SG(7,2047)
3328
computing SG(7,4095)
32768
computing SG(7,8191)
49152
computing SG(7,16383)
45056
computing SG(7,32767)
53248
computing SG(7,65535)
524288
computing SG(15,15)
24
computing SG(15,31)
44
computing SG(15,63)
75
computing SG(15,127)
141
computing SG(15,255)
4096
computing SG(15,511)
8192
computing SG(15,1023)
16384
computing SG(15,2047)
32768
computing SG(15,4095)
6144
computing SG(15,8191)
11264
computing SG(15,16383)
19200
computing SG(15,32767)
36096
computing SG(15,65535)
1048576
computing SG(31,31)
52
computing SG(31,63)
141
computing SG(31,127)
198
computing SG(31,255)
8192
computing SG(31,511)
12288
computing SG(31,1023)
32768
computing SG(31,2047)
49152
computing SG(31,4095)
11264
computing SG(31,8191)
13312
computing SG(31,16383)
36096
computing SG(31,32767)
50688
computing SG(31,65535)
2097152
computing SG(63,63)
103
computing SG(63,127)
185
computing SG(63,255)
16384
computing SG(63,511)
32768
computing SG(63,1023)
24576
computing SG(63,2047)
45056
computing SG(63,4095)
19200
computing SG(63,8191)
36096
computing SG(63,16383)
26368
computing SG(63,32767)
47360
computing SG(63,65535)
4194304
computing SG(127,127)
222
computing SG(127,255)
32768
computing SG(127,511)
49152
computing SG(127,1023)
45056
computing SG(127,2047)
53248
computing SG(127,4095)
36096
computing SG(127,8191)
50688
computing SG(127,16383)
47360
computing SG(127,32767)
56832
computing SG(127,65535)
8388608
computing SG(255,255)
384
computing SG(255,511)
704
computing SG(255,1023)
1200
computing SG(255,2047)
2256
computing SG(255,4095)
4237
computing SG(255,8191)
8390
computing SG(255,16383)
16569
computing SG(255,32767)
32990
computing SG(255,65535)
16777216
computing SG(511,511)
832
computing SG(511,1023)
2256
computing SG(511,2047)
3168
computing SG(511,4095)
8390
computing SG(511,8191)
12363
computing SG(511,16383)
32990
computing SG(511,32767)
49255
computing SG(511,65535)
33554432
computing SG(1023,1023)
1648
computing SG(1023,2047)
2960
computing SG(1023,4095)
16569
computing SG(1023,8191)
32990
computing SG(1023,16383)
24703
computing SG(1023,32767)
45205
computing SG(1023,65535)
https://ideone.com/Mh1hFM
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!