0
Your rating: None

CodeChef submission 130297 (C++ 4.0.0-8)

CodeChef submission 130297 (C++ 4.0.0-8) plaintext list. Status: WA, problem J7, contest NOV09. By balakrishnan_v (Balakrishnan Varadarajan), 2009-11-11 04:47:56.
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. int D,S;
  6. int B[502];
  7. bool M[502][502];
  8. int T[502];
  9. int l[501][502];
  10. int dl[501][502];
  11. int nextl[501][502];
  12. int nextdl[501][502];
  13. bool nextthere[501][502];
  14. int gains[501][502];
  15. bool there[501][502];
  16. int optswaps[501][502];
  17. int numexts[501];
  18. int totgains[502];
  19. int satis[502*501];
  20. int kval[502*501];
  21. int swapval[502*501];
  22. bool answer[502];
  23. int likes[502];
  24. int dislikes[502];
  25. int width;
  26. int kcurr;
  27. bool diff[90][90][502];
  28. int distance[90][90];
  29. int max(int a,int b){return a>b?a:b;}
  30. int min(int a,int b){return a<b?a:b;}
  31.  
  32. int main()
  33. {
  34.   scanf("%d %d",&D,&S);
  35.   for(int i=0;i<D;i++)
  36.     scanf("%d",&B[i]);
  37.   for(int i=0;i<D;i++)
  38.     for(int j=0;j<S;j++)
  39.       scanf("%d",&M[i][j]);
  40. 	
  41.   for(int i=0;i<D;i++)
  42.     {
  43.       l[0][i]=0;
  44.       dl[0][i]=0;
  45.     }
  46.   for(int i=0;i<S;i++)
  47.     there[0][i]=0;
  48.   satis[0]=0;
  49.   swapval[0]=-1;
  50.   width=500;
  51.   kcurr=1;
  52.   int maxsatis=-1;
  53.   for(int iters=1;iters<=30;iters++)
  54.     {
  55.       if(iters==2)
  56. 	width=400;
  57.       if(iters>2)
  58. 	width=50;
  59.       for(int i=0;i<=D;i++)
  60. 	totgains[i]=0;
  61. 		
  62.       if(iters>=4)
  63. 	{
  64.       for(int i=0;i<kcurr;i++)
  65. 	for(int j=0;j<kcurr;j++)
  66. 	  {
  67. 	    distance[i][j]=0;
  68. 	    for(int k=0;k<S;k++)
  69. 	      {
  70. 	      diff[i][j][k]=there[i][k]^there[j][k];
  71. 	      distance[i][j]+=there[i][k]^there[j][k];
  72. 	      }
  73. 	  }
  74. 	}
  75.  
  76.       for(int i=0;i<kcurr;i++)
  77. 	{
  78. 	  //printf("%d\n",iters);
  79. 	  // printf("%d %d %d %d %d\n",there[i][0],there[i][1],there[i][2],there[i][3],there[i][4]);
  80. 	  //printf("%d %d %d %d\n",l[i][0],l[i][1],l[i][2],l[i][3]);
  81. 	  //printf("%d %d %d %d\n",dl[i][0],dl[i][1],dl[i][2],dl[i][3]);
  82. 	  // printf("------------------\n");
  83. 	  for(int j=0;j<S;j++)
  84. 	    {
  85. 	      gains[i][j]=1000;
  86. 	      if(j==swapval[i])
  87. 		continue;
  88. 	      if(iters==2 && swapval[i]>j)
  89. 		continue;
  90. 		  
  91. 	      bool repeat=0;
  92. 	      if(iters>=4)
  93. 		{
  94. 	      for(int k=0;k<i;k++)
  95. 		{
  96. 		  if(distance[i][k]==2 && diff[i][k][j])
  97. 		    {
  98. 		      repeat=1;
  99. 		      //printf("sdfsdf\n");
  100. 		      break;
  101. 		    }
  102. 		}
  103. 		}
  104. 	      if(repeat)
  105. 	      	continue;
  106.  
  107.  
  108. 	      gains[i][j]=satis[i];
  109. 				
  110. 	      for(int k=0;k<D;k++)
  111. 		{
  112. 					
  113. 		  if(there[i][j])//going to remove
  114. 		    {
  115. 		      if(M[k][j] && l[i][k]==1 && dl[i][k]<B[k])
  116. 			gains[i][j]--;
  117. 		      if(!M[k][j] && l[i][k]>0 && dl[i][k]==B[k])
  118. 			gains[i][j]++;
  119. 		    }
  120. 		  else//going to add
  121. 		    {
  122. 		      if(M[k][j] && l[i][k]==0 && dl[i][k]<B[k])
  123. 			gains[i][j]++;
  124. 		      if(!M[k][j] && l[i][k]>0 && dl[i][k]==B[k]-1)
  125. 			gains[i][j]--;
  126. 		    }
  127. 					
  128. 					
  129. 		}
  130. 	      //printf("%d %d %d %d %d swapping %d initial=%d g=%d ,%d %d,iters=%d\n",there[i][0],there[i][1],there[i][2],there[i][3],there[i][4],j,satis[i],gains[i][j],dl[i][0],l[i][0],iters);
  131. 	      totgains[D-gains[i][j]]++;
  132. 	    }
  133. 	}
  134.       //gains can be from 0 to +D
  135. 		
  136.       for(int i=1;i<=D;i++)
  137. 	{
  138. 	  //printf("%d %d\n",i,totgains[i]);
  139. 	totgains[i]+=totgains[i-1];//cumulative frequency
  140. 	}
  141.       int size=totgains[D];
  142.       //printf("size=%d\n",size);
  143.       for(int i=0;i<kcurr;i++)
  144. 	{
  145. 	  for(int j=0;j<S;j++)//bucket sort
  146. 	    {
  147. 	      if(gains[i][j]>D)
  148. 		continue;
  149. 	      //else
  150. 	      //	{
  151. 	      //	  printf("%d %d\n",i,j);
  152. 	      //	}
  153. 	      satis[totgains[D-gains[i][j]]-1]=gains[i][j];
  154. 	      kval[totgains[D-gains[i][j]]-1]=i;
  155. 	      swapval[--totgains[D-gains[i][j]]]=j;
  156. 	    }
  157. 	}
  158.       int up=min(width,size)-1;
  159.       //printf("%d %d\n",up,totgains[D-satis[up]+1]-1);
  160.       //up=min(totgains[D-satis[up]+1]-1,40);
  161.  
  162.       for(int i=0;i<=up;i++)
  163. 	{
  164. 	  for(int j=0;j<S;j++)
  165. 	    {
  166. 	      nextthere[i][j]=there[kval[i]][j];
  167. 	      //printf("%d,",there[kval[i]][j]);
  168. 	    }
  169. 			
  170. 			
  171. 	  int j=swapval[i];
  172. 	  for(int k=0;k<D;k++)
  173. 	    {
  174. 	      nextl[i][k]=l[kval[i]][k];
  175. 	      nextdl[i][k]=dl[kval[i]][k];	      
  176. 	    }
  177. 	  for(int k=0;k<D;k++)
  178. 	    {
  179. 	      if(nextthere[i][j] && M[k][j])
  180. 		nextl[i][k]=l[kval[i]][k]-1;
  181. 	      if(nextthere[i][j] && !M[k][j])
  182. 		nextdl[i][k]=dl[kval[i]][k]-1;
  183. 	      if(!nextthere[i][j] && M[k][j])
  184. 		nextl[i][k]=l[kval[i]][k]+1;
  185. 	      if(!nextthere[i][j] && !M[k][j])
  186. 		nextdl[i][k]=dl[kval[i]][k]+1;
  187. 	    }
  188. 	  nextthere[i][j]=!nextthere[i][j];
  189. 			
  190. 	}
  191.       for(int i=0;i<=up;i++)
  192. 	{
  193. 	  for(int j=0;j<S;j++)
  194. 	    there[i][j]=nextthere[i][j];
  195. 	  for(int k=0;k<D;k++)
  196. 	    {
  197. 	      l[i][k]=nextl[i][k];
  198. 	      dl[i][k]=nextdl[i][k];
  199. 	    }
  200. 	  if(satis[i]>maxsatis)
  201. 	    {
  202. 	      for(int j=0;j<S;j++)
  203. 		answer[j]=there[i][j];
  204. 	      for(int j=0;j<D;j++)
  205. 		{
  206. 		  likes[j]=l[i][j];
  207. 		  dislikes[j]=dl[i][j];
  208. 		}
  209. 	      maxsatis=satis[i];
  210. 	    }
  211. 	}
  212. 		
  213.       kcurr=up-1;
  214. 		
  215.     }
  216.   int tot=0;
  217.   for(int i=0;i<S;i++)
  218.     {
  219.       tot+=answer[i];
  220.     }
  221. 	
  222.   for(int i=0;i<D;i++)
  223.     {
  224.       T[i]=1+max(0,tot-B[i]);
  225.     }
  226. 	
  227.   printf("%d\n",tot);
  228.   int S1[600];
  229.   int S2[600];
  230.   int val=maxsatis;
  231.   for(int iters=1;iters<=0;iters++)
  232.     {
  233.       int inival=val;
  234.       int S1size=0;
  235.       for(int i=0;i<D;i++)
  236. 	if(likes[i]==T[i]-1)
  237. 	  S1[S1size++]=i;
  238. 		
  239.       int maxcount=-1;
  240.       int iopt=-1;
  241.       for(int i=0;i<S;i++)
  242. 	{
  243. 	  if(!answer[i])
  244. 	    {
  245. 	      int count=0;
  246. 	      for(int j=0;j<S1size;j++)
  247. 		{
  248. 		  if(M[S1[j]][i])
  249. 		    {
  250. 		      count++;
  251. 		    }
  252. 		}
  253. 	      if(count>maxcount)
  254. 		{
  255. 		  iopt=i;
  256. 		  maxcount=count;
  257. 		}
  258. 	    }
  259. 	}
  260.       if(iopt==-1)
  261. 	break;
  262.       answer[iopt]=1;
  263.       //printf("--%d %d\n",maxcount,iopt);
  264.       val+=maxcount;
  265.       for(int j=0;j<D;j++)
  266. 	{
  267. 	  if(M[j][iopt])
  268. 	    likes[j]++;
  269. 	}
  270.       int S2size=0;
  271.       for(int i=0;i<D;i++)
  272. 	if(likes[i]==T[i])
  273. 	  S2[S2size++]=i;
  274.       iopt=-1;
  275.       maxcount=3000;
  276.       for(int i=0;i<S;i++)
  277. 	{
  278. 	  if(answer[i])
  279. 	    {
  280. 	      int count=0;
  281. 	      for(int j=0;j<S2size;j++)
  282. 		{
  283. 		  if(M[S2[j]][i])
  284. 		    count++;
  285. 		}
  286. 	      if(count<maxcount)
  287. 		{
  288. 		  iopt=i;
  289. 		  maxcount=count;
  290. 		}
  291. 	    }
  292. 	}
  293.       if(iopt==-1)
  294. 	break;
  295.       answer[iopt]=0;
  296.       for(int j=0;j<D;j++)
  297. 	{
  298. 	  if(M[j][iopt])
  299. 	    likes[j]--;
  300. 	}
  301.       //printf("^^%d\n",maxcount);
  302.       val-=maxcount;
  303.       //printf("%d %d\n",val,inival);	
  304.       if(val==inival)
  305.       	break;
  306. 		
  307. 		
  308.     }
  309. 	
  310. 	
  311. 	
  312.   for(int i=0;i<S;i++)
  313.     if(answer[i])
  314.       printf("%d\n",i);
  315. 	
  316.   //printf("satis=%d\n",maxsatis);
  317. 	
  318.   /*int val=0;
  319.     for(int i=0;i<D;i++)
  320.     {
  321.     int likes=0;
  322.     int dislikes=0;
  323.     //printf("error %d\n",l[i]);
  324. 	 
  325.     for(int j=0;j<S;j++)
  326.     {
  327.     if(answer[j])
  328.     {
  329.     if(M[i][j])
  330.     likes++;
  331.     else
  332.     dislikes++;
  333.     }
  334.     }
  335.     //if(likes!=l[i])
  336.     //printf("error %d %d %d\n",i,likes,l[i]);
  337.     if(likes>0 && dislikes<B[i])
  338.     val++;
  339.     }
  340. 	 
  341.     printf("%d\n",val);*/
  342. 	
  343. 	
  344. 	
  345. }
  346.

Comments