0
Your rating: None

CodeChef submission 108891 (C++ 4.0.0-8)

CodeChef submission 108891 (C++ 4.0.0-8) plaintext list. Status: TLE, problem HX, contest OCT09. By keshav_57 (Keshav Dhandhania), 2009-10-11 14:55:01.
  1.  
  2. // TO DO 
  3. // Think of something which is 'global'
  4. //       Like start from someplace with greater concentration of larger numbers
  5. // Check if repeating flip_two() will help, or make a queue out of this as well
  6.  
  7. #include<iostream>
  8. #include<fstream>
  9. #include<queue>
  10. #include<cstring>
  11. #include<algorithm>
  12. using namespace std;
  13.  
  14. #define sz 2010
  15. #define INF 100000000.0
  16. #define block 2
  17.  
  18. int n;
  19. float q[sz][sz];
  20. bool b[sz][sz];
  21. float sum[sz][sz];
  22. float SCORE[sz][sz];
  23. float SCOREc[sz][sz];
  24. int nx[7]; int ny[2][7];
  25.  
  26. float qdp[sz][sz];
  27. float cost[sz][(1<<block)];
  28. int prev[sz][(1<<block)];
  29. float sum3[sz][sz];
  30.  
  31. void modify(int &i, int &j)
  32. {
  33.    for (int k = 0; k < 6; k++)
  34.    if (b[i][j]==b[i+nx[k]][j+ny[(i&1)][k]]) SCORE[i+nx[k]][j+ny[(i&1)][k]] += q[i][j];
  35.    else SCORE[i+nx[k]][j+ny[(i&1)][k]] -= q[i][j];
  36. }
  37.  
  38. void modify3(int &i, int &j)
  39. {
  40.    for (int k = 0; k < 3; k++)
  41.    if (b[i][j]==b[i+nx[k]][j+ny[(i&1)][k]]) SCORE[i+nx[k]][j+ny[(i&1)][k]] += q[i][j];
  42.    else SCORE[i+nx[k]][j+ny[(i&1)][k]] -= q[i][j];
  43. }
  44.  
  45. void input()
  46. {
  47. 	scanf("%d\n", &n);
  48. 	char str[100000];
  49. 	int l = 0;
  50. 	float d;
  51. 	for (int i = 1; i <= n; i++)
  52. 	{
  53. 		gets(str);
  54. 		l = 0;
  55. 		for (int j = 1; j <= n; j++)
  56. 		{
  57. 			d = 1.0; q[i][j] += d*(str[l]-'0');
  58. 			while (1)
  59. 			{
  60. 				l++;
  61. 				if (str[l] == ' ' || str[l] == '\0') break;
  62. 				else if (str[l] >= '0' && str[l] <= '9') 
  63. 				{ d /= 10.0; q[i][j] += (str[l]-'0')*d; }
  64. 			}
  65. 			l++;
  66. 		}
  67. 	}
  68. }
  69.  
  70. void output()
  71. {
  72.      char str[10000];
  73.      memset(str, ' ', sizeof(str));
  74.      str[2*n] = '\0';
  75.      for (int i = 1; i <= n; i++)
  76.      {
  77.          for (int j = 1; j <= n; j++)
  78.              str[2*(j-1)] = '0' + (b[i][j]?1:0);
  79.          puts(str);
  80.      }
  81. }
  82.  
  83. void init()
  84. {
  85.      nx[1] = nx[2] = -1; nx[4] = nx[5] = 1;
  86.      ny[1][1] = ny[1][5] = -1; 
  87.      ny[0][2] = ny[0][4] = 1;
  88.      ny[1][0] = ny[0][0] = -1;
  89.      ny[1][3] = ny[0][3] = 1;
  90.      for (int i = 1; i <= n; i++)
  91.          for (int j = 1; j <= n; j++)
  92.              for (int k = 0; k < 6; k++)
  93.              {
  94.                  if (k==3) sum3[i][j] = sum[i][j];
  95.                  sum[i][j] += q[i+nx[k]][j+ny[(i&1)][k]];
  96.              }
  97. }
  98.  
  99. void score (int i, int j)
  100. {
  101.      SCORE[i][j] = 0.0;
  102.      for (int k = 0; k < 6; k++)
  103.          if (b[i+nx[k]][j+ny[(i&1)][k]]==b[i][j]) 
  104.             SCORE[i][j] += q[i+nx[k]][j+ny[(i&1)][k]];
  105. }
  106.  
  107. void score3 (int &i, int j, float &r1, float &r2)
  108. {
  109.      r1 = 0.0;
  110.      for (int k = 0; k < 3; k++)
  111.          if (b[i+nx[k]][j+ny[(i&1)][k]]==b[i][j]) 
  112.             r1 += q[i+nx[k]][j+ny[(i&1)][k]];
  113.      r2 = sum3[i][j] - r1;
  114. }
  115.  
  116. void scoreref3 (int &i, int &j, float &r1, float &r2)
  117. {
  118.      r1 = 0.0;
  119.      for (int k = 0; k < 3; k++)
  120.          if (b[i+nx[k]][j+ny[(i&1)][k]]==b[i][j]) 
  121.             r1 += q[i+nx[k]][j+ny[(i&1)][k]];
  122.      r2 = sum3[i][j] - r1;
  123. }
  124.  
  125. void scoreref (int &i, int &j)
  126. { 
  127.      SCORE[i][j] = 0.0;
  128.      for (int k = 0; k < 6; k++)
  129.          if (b[i+nx[k]][j+ny[(i&1)][k]]==b[i][j]) 
  130.             SCORE[i][j] += q[i+nx[k]][j+ny[(i&1)][k]];
  131. }
  132.  
  133. void flip_one_queue()
  134. {
  135. 	float r1, r2;
  136. 	queue <int> x; 
  137.     queue <int> y;
  138. 	int px, py;
  139. 	for (int i = 1; i <= n; i++)
  140. 		for (int j = 1; j <= n; j++)
  141. 		{
  142.             scoreref(i, j); 
  143. 			if (sum[i][j]-SCORE[i][j] < SCORE[i][j]) 
  144.             {
  145.                    b[i][j] = !b[i][j];
  146.                    SCORE[i][j] = sum[i][j]-SCORE[i][j];
  147.                    modify3(i,j);
  148.                    for (int k = 0; k < 3; k++) 
  149.                        { 
  150.                           x.push(i+nx[k]); 
  151.                           y.push(j+ny[(i&1)][k]); 
  152.                        }
  153. // the rest three are later, so they are automatically checked; dont push them; 
  154.             }
  155. 		}
  156. 	while (!x.empty())
  157. 	{
  158.           px = x.front();
  159.           py = y.front();
  160.           x.pop(); y.pop(); 
  161.           if (px < 1 || px > n || py < 1 || py > n) continue;
  162.           if (sum[px][py]-SCORE[px][py] < SCORE[px][py]) 
  163.           {
  164.              SCORE[px][py] = sum[px][py]-SCORE[px][py];
  165.              b[px][py] = !b[px][py];
  166.              modify(px,py);
  167.              for (int k = 0; k < 6; k++)
  168.                  { 
  169.                     x.push(px+nx[k]); 
  170.                     y.push(py+ny[(px&1)][k]); 
  171.                  }
  172.           }
  173.     }
  174. }
  175.  
  176. void flip_one_queue2()
  177. {
  178. 	float r1, r2;
  179. 	queue <int> x; 
  180.     queue <int> y;
  181. 	int px, py;
  182. 	for (int i = 1; i <= n; i++)
  183. 		for (int j = 1; j <= n; j++)
  184. 		{
  185. 			if (sum[i][j]-SCORE[i][j] < SCORE[i][j]) 
  186.             {
  187.                    b[i][j] = !b[i][j];
  188.                    SCORE[i][j] = sum[i][j]-SCORE[i][j];
  189.                    modify(i,j);
  190.                    for (int k = 0; k < 3; k++) 
  191.                        { 
  192.                           x.push(i+nx[k]); 
  193.                           y.push(j+ny[(i&1)][k]); 
  194.                        }
  195. // the rest three are later, so they are automatically checked; dont push them; 
  196.             }
  197. 		}
  198. 	while (!x.empty())
  199. 	{
  200.           px = x.front();
  201.           py = y.front();
  202.           x.pop(); y.pop(); 
  203.           if (px < 1 || px > n || py < 1 || py > n) continue;
  204.           if (sum[px][py]-SCORE[px][py] < SCORE[px][py]) 
  205.           {
  206.              SCORE[px][py] = sum[px][py]-SCORE[px][py];
  207.              b[px][py] = !b[px][py];
  208.              modify(px,py);
  209.              for (int k = 0; k < 6; k++)
  210.                  { 
  211.                     x.push(px+nx[k]); 
  212.                     y.push(py+ny[(px&1)][k]); 
  213.                  }
  214.           }
  215.     }
  216. }
  217.  
  218. void dp()
  219. {
  220.      int rem = n%block;
  221.      int width = n + (rem?block-rem:0);
  222.      
  223.      int bitmask[(1<<block)]; bitmask[0] = 0;
  224.      for (int i = 1; i < (1<<block); i++) bitmask[i] = (bitmask[i-1]^(i&(-i)));
  225.      
  226.      float cur; 
  227.      float r1, r2;
  228.      int start, end;
  229.      float addi;
  230.      int exp = (1<<block);
  231.      int i, j, k;
  232.  
  233.      for (int c = 0; c < (width/block); c++)
  234.      {
  235.          memset(cost, 125, sizeof(cost));
  236.          cost[0][0] = 0.0;
  237.          
  238.          start = c*block + 1; end = start + 1; 
  239.          for (i = 1; i <= n; i++)
  240.          {
  241.              qdp[i][start] = q[i][start];
  242.              qdp[i][end] = q[i][end];
  243.          }
  244.          for (i = 1; i <= n+1; i++)
  245.              for (j = 0; j < exp; j++) // state of prev row
  246.              {
  247.                  addi = 0.0;
  248.                  cur = 0.0;
  249.                  b[i][start] = b[i][end] = false;
  250.                  b[i-1][start] = ((1&j)?true:false);
  251.                  b[i-1][end] = ((2&j)?true:false);
  252.                  scoreref3(i,start,r1,r2);
  253.                  cur += r1*qdp[i][start];
  254.                  scoreref3(i,end,r1,r2);
  255.                  cur += r1*qdp[i][end];
  256.                  
  257.                  if (i&1) if (!b[i+1][start-1]) addi = q[i][j]*q[i+1][start-1];
  258.                  if (cost[i][0] > cost[i-1][j]+cur+addi)
  259.                  {
  260.                     cost[i][0] = cost[i-1][j]+cur+addi;
  261.                     prev[i][0] = j;
  262.                  }
  263.                  for (k = 1; k < exp; k++)
  264.                  {
  265.                      if (k&1)
  266.                      {
  267.                          scoreref3(i,start,r1,r2);
  268.                          b[i][start] ^= 1;
  269.                          cur += qdp[i][start]*(r2-r1);
  270.                      }
  271.                      else
  272.                      {
  273.                          scoreref3(i,end,r1,r2);
  274.                          b[i][end] ^= 1;
  275.                          cur += qdp[i][end]*(r2-r1);
  276.                      }                     
  277.                      addi = (((i&1)&&(b[i+1][start-1]^(bitmask[k]&1)))?q[i][j]*q[i+1][start-1]:0.0);
  278.                      if (cost[i][bitmask[k]] > cost[i-1][j]+cur+addi)
  279.                      {
  280.                         cost[i][bitmask[k]] = cost[i-1][j]+cur+addi;
  281.                         prev[i][bitmask[k]] = j;
  282.                      }
  283.                  }
  284.              }
  285.          int now = 0;
  286.          for (i = n; i >= 1; i--)
  287.          {
  288.              now = prev[i+1][now];
  289.              for (int j = 0; j < block; j++)
  290.                  if ((1<<j)&now) b[i][start+j] = true;
  291.                  else b[i][start+j] = false;
  292.          }
  293.      }
  294. }
  295.  
  296. void flip_two()
  297. {
  298.      float af, bf, cf, df;
  299.      int tempi, tempj;
  300.      bool v; 
  301.      if (n < 1851)
  302.      {
  303.          for (int i = 2; i <= n; i++)
  304.              for (int j = 1; j <= n; j++)
  305.                  for (int k = 0; k < 3; k++)
  306.                  {
  307.                      v = (b[i][j]==b[i+nx[k]][j+ny[(i&1)][k]]);
  308.         			 if 
  309.                      ((sum[i][j] - SCORE[i][j] - (!v?q[i+nx[k]][j+ny[(i&1)][k]]:0.0))*q[i][j] + 
  310.                      (sum[i+nx[k]][j+ny[(i&1)][k]] - SCORE[i+nx[k]][j+ny[(i&1)][k]] - (!v?q[i][j]:0.0))*q[i+nx[k]][j+ny[(i&1)][k]] < 
  311.                      (SCORE[i][j] - (v?q[i+nx[k]][j+ny[(i&1)][k]]:0.0))*q[i][j] + 
  312.                      (SCORE[i+nx[k]][j+ny[(i&1)][k]] - (v?q[i][j]:0.0))*q[i+nx[k]][j+ny[(i&1)][k]]) 
  313.                      { 
  314.                         b[i][j] = !b[i][j]; b[i+nx[k]][j+ny[(i&1)][k]] = !b[i+nx[k]][j+ny[(i&1)][k]]; 
  315.                          modify(i,j); tempi = i+nx[k]; tempj = j+ny[(i&1)][k];
  316.                          modify(tempi,tempj);
  317.                          scoreref(i,j);
  318.                          scoreref(tempi,tempj);                        
  319.                      }
  320.                  }
  321.      }
  322.      else
  323.      {
  324.          for (int i = 1; i <= n; i++)
  325.              for (int j = 2; j <= n; j++)
  326.                  {
  327.                      if ((sum[i][j] - SCORE[i][j] - (!v?q[i][j-1]:0.0))*q[i][j] + 
  328.                      (sum[i][j-1] - SCORE[i][j-1] - (!v?q[i][j]:0.0))*q[i][j-1] < 
  329.                      (SCORE[i][j] - (v?q[i][j-1]:0.0))*q[i][j] + 
  330.                      (SCORE[i][j-1] - (v?q[i][j]:0.0))*q[i][j-1]) 
  331.                       { 
  332.                          b[i][j] = !b[i][j]; b[i][j-1] = !b[i][j-1]; 
  333.                          modify(i,j);
  334.                          tempj = j-1;
  335.                          modify(i,tempj);
  336.                          scoreref(i,j);
  337.                          score(i,tempj);
  338.                       }
  339.                  }
  340.      }
  341. }
  342.  
  343. int main()
  344. {
  345. 	input();
  346.     init(); dp();
  347. 	flip_one_queue();
  348. 	if (n < 1951)
  349. 	{
  350.        	flip_two();
  351.        	flip_one_queue2();
  352.     }
  353. 	output(); 
  354. 	return 0;
  355. }
  356. /*
  357. int main ()
  358. {
  359. 	char test_str[15] = "FC .txt\0";
  360. 	char test_str2[15] = "9FC .txt\0";
  361. 	double sc = 0.0, sc2 = 0.0;
  362. 	ofstream result;
  363. 	result.open("R9FlipTwo2.txt");
  364. 	for (int test = 0; test < 10; test++)
  365. 	{
  366. 		sc = 0.0;
  367. 		n = 0;
  368. 		memset(q, 0, sizeof(q));
  369. 		memset(b, 0, sizeof(b));
  370. 		memset(sum, 0, sizeof(sum));
  371. 		memset(qdp, 0, sizeof(qdp));
  372. 		memset(prev, 0, sizeof(prev));
  373. 		memset(cost, 0, sizeof(cost));
  374. 		memset(sum3, 0, sizeof(sum3));
  375. 		test_str[2] = test_str2[3] = test+'0';
  376. 		freopen(test_str, "r", stdin);
  377. 		freopen(test_str2, "w", stdout);
  378. 		printf("\n");
  379. 		MAIN();
  380. 		for (int i = 1; i <= n; i++)
  381. 			for (int j = 1; j <= n; j++)
  382. 				sc += q[i][j-1]*q[i][j]*((b[i][j-1]==b[i][j])?1.0:0.0) + q[i-1][j]*q[i][j]*((b[i-1][j]==b[i][j])?1.0:0.0) + q[i-1][(i%2?j-1:j+1)]*q[i][j]*((b[i-1][(i%2?j-1:j+1)]==b[i][j])?1.0:0.0);
  383. 		sc2 += sc;
  384. 		result << sc << endl;
  385. 		fclose(stdin);
  386. 		fclose(stdout);
  387. 	}
  388. 	sc2 /= 10.0;
  389. 	result << endl << sc2 << endl;
  390. 	result.close();
  391. 	return 0;
  392. }
  393. */
  394. // 1421158.892623
  395.

Comments