0
Your rating: None

CodeChef submission 131081 (C++ 4.0.0-8)

CodeChef submission 131081 (C++ 4.0.0-8) plaintext list. Status: AC, problem JX, contest NOV09. By anshuman_singh (Anshuman Singh), 2009-11-11 14:55:11.
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<map>
  6. #include<vector>
  7. #include<list>
  8. #include<set>
  9. #include<queue>
  10. #include<cassert>
  11. #include<sstream>
  12. #include<string>
  13. #include<cmath>
  14. #include<algorithm>
  15. #include<climits>
  16. using namespace std;
  17.  
  18. #define LET(x,a) 	__typeof(a) x(a)
  19. #define IFOR(i,a,b) 	for(LET(i,a);i!=(b);++i)
  20. #define EACH(it,v)  	IFOR(it,v.begin(),v.end())
  21. #define FOR(i,a,b)  	for(int i=(int)(a) ; i < (int)(b);++i)
  22. #define REP(i,n) 	FOR(i,0,n)
  23. #define PB		push_back
  24. #define MP 		make_pair
  25. #define EPS		1e-9
  26. #define INF 2000000000
  27.  
  28. typedef vector<int>	VI;
  29. typedef long long	LL;
  30. typedef pair<int,int>	PI;
  31.  
  32.  
  33. #define BUFSIZE (1000000)
  34. char outputbuffer[BUFSIZE<<1],inputbuffer[BUFSIZE];
  35. char *outptr=outputbuffer,*ioptr=inputbuffer+BUFSIZE,*ioend=inputbuffer+BUFSIZE;
  36. int input_eof=0;
  37.  
  38. #define putchar(c) (*outptr++ = (c))
  39. #define getchar() ({if (ioptr >= ioend) init_input(); *ioptr++;})
  40. #define eof() (ioptr>=ioend && input_eof)
  41. #define eoln() ({if(ioptr >= ioend) init_input(); *ioptr == '\n';})
  42.  
  43. void init_input(){
  44. 	if (input_eof)
  45. 		return;
  46. 	int existing = BUFSIZE - (ioend - inputbuffer);
  47. 	memcpy(inputbuffer, ioend, existing);
  48. 	int wanted = ioend - inputbuffer;
  49. 	int count=fread(inputbuffer + existing, 1, wanted, stdin);
  50. 	if (count < wanted)
  51. 		input_eof = 1;
  52. 	ioend = inputbuffer + BUFSIZE - (wanted - count);
  53. 	while (*--ioend > ' ');
  54. 	ioend++;
  55. 	ioptr=inputbuffer;
  56. }
  57.  
  58. inline void non_whitespace(){
  59. 	for(;;){
  60. 		if(ioptr>=ioend)
  61. 			init_input();
  62. 		if(*ioptr>' ')
  63. 			return;
  64. 		ioptr++;
  65. 	}
  66. }
  67.  
  68. void flush_output(){
  69. 	fwrite(outputbuffer,1,outptr-outputbuffer,stdout);
  70. 	outptr=outputbuffer;
  71. }
  72.  
  73. inline void check_output(){
  74. 	if(outptr>=outputbuffer+BUFSIZE)
  75. 		flush_output();
  76. }
  77.  
  78. inline int getint(){
  79. 	non_whitespace();
  80. 	int neg=0;
  81. 	if(*ioptr=='-'){
  82. 		ioptr++;
  83. 		neg=1;
  84. 	}
  85. 	int n=0;
  86. 	while(*ioptr>' ')
  87. 		n=(n<<3)+(n<<1)+*ioptr++-'0';
  88. 	ioptr++;
  89. 	if(neg)
  90. 		n=-n;
  91. 	return n;
  92. }
  93.  
  94. inline void putint(int n){
  95. 	char buffer[10];
  96. 	int i=0,n2;
  97. 	do{
  98. 		n2=n/10;
  99. 		buffer[i++]=n-(n2<<3)-(n2<<1)+'0';
  100. 	}while((n=n2));
  101. 	while(i)
  102. 		putchar(buffer[--i]);
  103. 	check_output();
  104. }
  105. inline void putstr(char *str){
  106. 	int i=0;
  107. 	while(str[i]){putchar(str[i]);i++;}
  108. 	check_output();
  109. 	return;
  110. }
  111.  
  112. int d,s;
  113. int b[1000],like[1000],dislike[1000],present[1000],ind;	
  114. int M[501][501];//[song][dancers]
  115. bool taken[501],tempTaken[501],tempTaken2[501],tempTaken3[501];
  116. int globalScore=0;
  117.  
  118.  
  119. int findScore(){
  120. 	int score=0;
  121. 	REP(i,d)if(like[i] && dislike[i]<b[i])score++;
  122. 	return score;
  123. }
  124.  
  125. void Update(){
  126. 	int Score=findScore();
  127. 	if(Score>globalScore){
  128. 		globalScore=Score;
  129. 		REP(i,s)taken[i]=tempTaken[i];
  130. 	}
  131. 	return;
  132. }
  133.  
  134. void discard(int i){
  135. 	REP(j,d){
  136. 		if(M[i][j])like[j]--;
  137. 		else dislike[j]--;
  138. 	}
  139. 	tempTaken[i]=0;
  140. 	return;
  141. }
  142.  
  143. void doIter(){
  144. 	while(1){
  145. 		int maxscore=0;
  146. 		int maxIndex=-1;
  147. 		REP(i,s){
  148. 			if(tempTaken[i])continue;
  149. 			int score=0,score2=0;
  150. 			REP(j,d){
  151. 				if(dislike[j]>=b[j])continue;
  152. 				if(!like[j] && M[i][j]){
  153. 					score+=10000;score2++;continue;
  154. 				}
  155. 				if(!M[i][j] && dislike[j]==b[j]-1 && like[j]){
  156. 					score2--;score-=10000;continue;
  157. 				}
  158. 				if(M[i][j]){
  159. 					score+=(10000/(b[j]-dislike[j]));continue;
  160. 				}
  161. 			}
  162. 			if(score2>0 && score>maxscore){
  163. 				maxscore=score;
  164. 				maxIndex=i;
  165. 			}
  166. 		}
  167. 		if(maxscore<10)break;
  168. 		tempTaken[maxIndex]=1;
  169. 		REP(i,d){
  170. 			if(M[maxIndex][i])like[i]++;
  171. 			else dislike[i]++;
  172. 		}
  173. 	}
  174. 	return;
  175. }
  176.  
  177. void doIter2(){
  178. 	int maxscore2=-1;
  179. 	while(1){
  180. 		int maxscore=0,maxIndex=-1;
  181. 		REP(i,s)if(tempTaken[i] && !tempTaken3[i]){
  182. 			int score=0;
  183. 			REP(j,d){
  184. 				if(M[i][j] && like[j]==1 && dislike[j]<b[j])score++;
  185. 				if(!M[i][j] && like[j] && dislike[j]==b[j])score--;
  186. 			}
  187. 			if(score>maxscore){
  188. 				maxscore=score;
  189. 				maxIndex=i;
  190. 			}
  191. 		}
  192. 		if(maxscore < maxscore2 && maxIndex!=-1){
  193. 			discard(maxIndex);
  194. 			continue;
  195. 		}
  196. 		maxscore=0;maxIndex=-1;maxscore2=0;
  197. 		REP(i,s){
  198. 			if(tempTaken[i]||tempTaken3[i])continue;
  199. 			int score=0,score2=0;
  200. 			REP(j,d){
  201. 				if(dislike[j]>=b[j])continue;
  202. 				if(!like[j] && M[i][j]){
  203. 					score+=10000;score2++;continue;
  204. 				}
  205. 				if(!M[i][j] && dislike[j]==b[j]-1 && like[j]){
  206. 					score2--;score-=10000;continue;
  207. 				}
  208. 				if(M[i][j]){
  209. 					score+=(10000/(b[j]-dislike[j]));continue;
  210. 				}
  211. 			}
  212. 			if(score2>0 && score2>maxscore2){
  213. 				maxscore=score;
  214. 				maxscore2=score2;
  215. 				maxIndex=i;
  216. 			}
  217. 			else if(score2>0 && ((score2==maxscore2||score2==maxscore2-1) && score>maxscore)){
  218. 				maxscore=score;
  219. 				maxscore2=score2;
  220. 				maxIndex=i;
  221. 			}
  222. 		}
  223. 		if(maxscore2<1)break;
  224. 		tempTaken[maxIndex]=1;
  225. 		REP(i,d){
  226. 			if(M[maxIndex][i])like[i]++;
  227. 			else dislike[i]++;
  228. 		}
  229. 	}
  230. 	return;
  231. }
  232.  
  233. int findScore2(int ind){
  234. 	int ret=0;
  235. 	REP(i,d){
  236. 		if(M[ind][i])ret+=100000;
  237. 		else {
  238. 			if(b[i])ret-=100000/b[i];
  239. 		}
  240. 	}
  241. 	return ret;
  242. }
  243.  
  244.  
  245. void process2(){
  246. 	memset(tempTaken3,0,sizeof(tempTaken3));
  247. 	bool visited[501];memset(visited,0,sizeof(visited));
  248. 	if(s<30||d<30)return;
  249. 	for(int x=11;x<=200;x+=20){
  250. 		if(x>=s)continue;
  251. //	REP(i,10){
  252. //		int x=rand()%s;
  253. //		if(visited[x])while(visited[x])x=rand()%s;
  254. //		visited[x]=1;
  255. 		tempTaken3[x]=1;
  256. 		REP(i,s)tempTaken[i]=0;
  257. 		REP(i,d)like[i]=dislike[i]=0;
  258. 		doIter2();
  259. 		Update();
  260. 		tempTaken3[x]=0;
  261. 	}
  262. 	return;
  263. }
  264.  
  265. void process3(){
  266. 	memset(tempTaken2,0,sizeof(tempTaken2));
  267. 	bool visited[501];memset(visited,0,sizeof(visited));
  268. 	FOR(i,160,500)visited[i]=1;
  269. 	if(s<30||d<30)return;
  270. 	int toTry[]={19,25,36,44,49,81,97,100,121,144};
  271. 	int lim = min(s,160);
  272. 	REP(ii,15){
  273. //		int x=order[ii].second;
  274. 	//REP(i,15){
  275. 		int x=rand()%lim;
  276. 		if(ii>=5 && !visited[toTry[ii-5]])x=toTry[ii-5];
  277. 		if(visited[x])while(visited[x])x=rand()%lim;
  278. 		visited[x]=1;
  279. 		if(x>=s)continue;
  280. 		tempTaken2[x]=1;
  281. 		REP(i,s)tempTaken[i]=0;
  282. 		REP(i,d)like[i]=dislike[i]=0;
  283. 		tempTaken[x]=1;
  284. 		REP(i,d){
  285. 			if(M[x][i])like[i]++;
  286. 			else dislike[i]++;
  287. 		}
  288. 		doIter2();
  289. 		Update();
  290. 		tempTaken2[x]=0;
  291. 	}
  292. 	return;
  293. }
  294.  
  295. void process12(){
  296. 	memset(tempTaken3,0,sizeof(tempTaken3));
  297. 	bool visited[101];memset(visited,0,sizeof(visited));
  298. 	int lim = min(22,s/2);
  299. 	REP(i,lim){
  300. 		int x=rand()%s;
  301. 		if(visited[x])while(visited[x])x=rand()%s;
  302. 		visited[x]=1;
  303. 		tempTaken3[x]=1;
  304. 		REP(i,s)tempTaken[i]=0;
  305. 		REP(i,d)like[i]=dislike[i]=0;
  306. 		doIter2();
  307. 		Update();
  308. 		tempTaken3[x]=0;
  309. 	}
  310. 	return;
  311. }
  312.  
  313. void process13(){
  314. 	memset(tempTaken3,0,sizeof(tempTaken3));
  315. 	bool visited[101];memset(visited,0,sizeof(visited));
  316. 	int lim = min(22,s/2);
  317. 	REP(i,lim){
  318. 		int x=rand()%s;
  319. 		if(visited[x])while(visited[x])x=rand()%s;
  320. 		visited[x]=1;
  321. 		tempTaken2[x]=1;
  322. 		REP(i,s)tempTaken[i]=0;
  323. 		REP(i,d)like[i]=dislike[i]=0;
  324. 		tempTaken[x]=1;
  325. 		REP(i,d){
  326. 			if(M[x][i])like[i]++;
  327. 			else dislike[i]++;
  328. 		}
  329. 		doIter2();
  330. 		Update();
  331. 		tempTaken2[x]=0;
  332. 	}
  333. 	return;
  334. }
  335.  
  336.  
  337. void reset(){
  338. 	REP(i,s)tempTaken[i]=taken[i];
  339. 	REP(j,d)like[j]=dislike[j]=0;
  340. 	REP(i,s)if(tempTaken[i])REP(j,d){
  341. 		if(M[i][j])like[j]++;
  342. 		else dislike[j]++;
  343. 	}
  344. 	return;
  345. }
  346.  
  347.  
  348. PI order[501];
  349. bool changed;
  350. int main(){
  351. 	init_input();
  352. 	d=getint();
  353. 	s=getint();
  354. 	REP(i,d){
  355. 		b[i]=getint();
  356. 		b[i]=min(s+1,b[i]);
  357. 	}
  358. 	REP(i,d)REP(j,s)M[j][i]=getint();
  359. 	memset(taken,0,sizeof(taken));
  360. 	memset(like,0,sizeof(like));
  361. 	memset(dislike,0,sizeof(dislike));
  362. 	globalScore=0;
  363. 	/***************** Method 1 **************************************/
  364. 	doIter();
  365. 	Update();
  366. 	fprintf(stderr,"Method 1.5: %d\n",globalScore);
  367. 	/***********************************Method 1 ends here **********************************/
  368. 	if(d>70){
  369. 		process2();
  370. 		process3();
  371. 		fprintf(stderr,"Method 1.5: %d\n",globalScore);
  372. 	}
  373. 	else {
  374. 		process12();
  375. 	//	process13();
  376. 		fprintf(stderr,"Method 1.5: %d\n",globalScore);
  377. 	}
  378. 	/****************** Trying to improve initial approach**********************************/
  379. 	if(s<=60 && d<=60){
  380. 		REP(i,s)tempTaken[i]=0;
  381. 		REP(i,d)like[i]=dislike[i]=0;
  382. 		int mscore=0,mscore2=0;
  383. 		int p1,p2,p3;
  384. 		REP(i,s)FOR(j,i+1,s)FOR(k,j+1,s){
  385. 			int score=0,score2=0;
  386. 			REP(l,d){
  387. 				int lik=0,dis=0;
  388. 				if(M[i][l])lik++;else dis++;
  389. 				if(M[j][l])lik++;else dis++;
  390. 				if(M[k][l])lik++;else dis++;
  391. 				if(lik)score2+=10000;
  392. 				if(dis>=b[l])score2-=10000;
  393. 				else score+=(10000/(b[l]-dis));
  394. 			}
  395. 			if(score2>mscore2 || (score2==mscore2 && score>mscore)){
  396. 				mscore=score;
  397. 				mscore2=score2;
  398. 				p1=i;p2=j;p3=k;
  399. 			}
  400. 		}
  401. 		if(mscore2<=0){
  402. 			reset();
  403. 		}
  404. 		else {
  405. 			tempTaken[p1]=1;
  406. 			tempTaken[p2]=1;
  407. 			tempTaken[p3]=1;
  408. 			REP(i,d){
  409. 				if(M[p1][i])like[i]++;else dislike[i]++;
  410. 				if(M[p2][i])like[i]++;else dislike[i]++;
  411. 				if(M[p3][i])like[i]++;else dislike[i]++;
  412. 			}
  413. 			doIter();
  414. 			Update();
  415. 		}
  416. 	}
  417. 	if(s<=400) {
  418. 		REP(i,s)tempTaken[i]=0;
  419. 		REP(i,d)like[i]=dislike[i]=0;
  420. 		int mscore=0,mscore2=0;
  421. 		int p1,p2;
  422. 		REP(i,s)FOR(j,i+1,s){
  423. 			int score=0,score2=0;
  424. 			REP(l,d){
  425. 				int lik=0,dis=0;
  426. 				if(M[i][l])lik++;else dis++;
  427. 				if(M[j][l])lik++;else dis++;
  428. 				if(lik)score2+=10000;
  429. 				if(dis>=b[l])score2-=10000;
  430. 				else score+=(10000/(b[l]-dis));
  431. 			}
  432. 			if(score2>mscore2 || (score2==mscore2 && score>mscore)){
  433. 				mscore=score;
  434. 				mscore2=score2;
  435. 				p1=i;p2=j;
  436. 			}
  437. 		}
  438. 		if(mscore2<=0){
  439. 			reset();
  440. 		}
  441. 		else {
  442. 			tempTaken[p1]=1;
  443. 			tempTaken[p2]=1;
  444. 			REP(i,d){
  445. 				if(M[p1][i])like[i]++;else dislike[i]++;
  446. 				if(M[p2][i])like[i]++;else dislike[i]++;
  447. 			}
  448. 			doIter();
  449. 			Update();
  450. 		}
  451.  
  452. 	}
  453. 	fprintf(stderr,"Method 1.5: %d\n",globalScore);
  454. 	reset();
  455. 	/********************************** Trying Method 2 here ********************************/
  456. 	changed=true;
  457. 	while(changed){
  458. 		changed=false;
  459. 		REP(i,s)tempTaken2[i]=tempTaken[i];	
  460. 		REP(i,s)if(tempTaken[i]){
  461. 			discard(i);
  462. 			doIter();	
  463. 			Update();
  464. 		}
  465. 		REP(i,s)if(tempTaken2[i]!=tempTaken[i])changed=true;
  466. 	}
  467. 	/**********************************Method 2 ends here ***********************************/
  468.  
  469. 	int iter=0;
  470. 	while(iter<8){
  471. 		iter++;
  472. 		if(d<=100)srand(time(NULL)+iter);
  473. 		/*********************************One more method ***************************************/
  474. 		reset();
  475. 		ind=0;
  476. 		REP(i,s)if(tempTaken[i])present[ind++]=i;
  477. 		REP(i,50){
  478. 			if(ind<=2)break;
  479. 			int a1 = rand()%ind,a2=a1;
  480. 			while(a2==a1)a2=rand()%ind;
  481. 			a1 = present[a1];
  482. 			a2 = present[a2];
  483. 			discard(a1);discard(a2);
  484. 			doIter();
  485. 			Update();
  486. 			ind=0;
  487. 			REP(i,s)if(tempTaken[i])present[ind++]=i;
  488. 		}
  489. 		reset();
  490. 		ind=0;
  491. 		REP(i,s)if(tempTaken[i])present[ind++]=i;
  492. 		REP(i,60){
  493. 			if(ind<=3)break;
  494. 			int a1 = rand()%ind,a2=a1,a3=a1;
  495. 			while(a2==a1)a2=rand()%ind;
  496. 			while(a3==a1||a3==a2)a3=rand()%ind;
  497. 			a1 = present[a1];
  498. 			a2 = present[a2];
  499. 			a3 = present[a3];
  500. 			discard(a1);discard(a2);discard(a3);
  501. 			doIter();
  502. 			Update();
  503. 			ind=0;
  504. 			REP(i,s)if(tempTaken[i])present[ind++]=i;
  505. 		}
  506. 		reset();
  507. 		ind=0;
  508. 		REP(i,s)if(tempTaken[i])present[ind++]=i;
  509. 		int lim=10;
  510. 		if(d<=100)lim=15;
  511. 		REP(i,lim){
  512. 			if(ind<=4)break;
  513. 			int a1 = rand()%ind,a2=a1,a3=a1,a4=a1;
  514. 			while(a2==a1)a2=rand()%ind;
  515. 			while(a3==a1||a3==a2)a3=rand()%ind;
  516. 			while(a4==a1||a4==a2||a4==a3)a4=rand()%ind;
  517. 			a1 = present[a1];
  518. 			a2 = present[a2];
  519. 			a3 = present[a3];
  520. 			a4 = present[a4];
  521. 			discard(a1);discard(a2);discard(a3);discard(a4);
  522. 			doIter();
  523. 			Update();
  524. 			ind=0;
  525. 			REP(i,s)if(tempTaken[i])present[ind++]=i;
  526. 		}
  527. 		reset();
  528. 		ind=0;
  529. 		REP(i,s)if(tempTaken[i])present[ind++]=i;
  530. 		lim=4;
  531. 		if(d<=100)lim=8;
  532. 		REP(i,lim){
  533. 			if(ind<=5)break;
  534. 			int a1 = rand()%ind,a2=a1,a3=a1,a4=a1,a5=a1;
  535. 			while(a2==a1)a2=rand()%ind;
  536. 			while(a3==a1||a3==a2)a3=rand()%ind;
  537. 			while(a4==a1||a4==a2||a4==a3)a4=rand()%ind;
  538. 			while(a5==a1||a5==a2||a5==a3||a5==a4)a5=rand()%ind;
  539. 			a1 = present[a1];
  540. 			a2 = present[a2];
  541. 			a3 = present[a3];
  542. 			a4 = present[a4];
  543. 			a5 = present[a5];
  544. 			discard(a1);discard(a2);discard(a3);discard(a4);discard(a5);
  545. 			doIter();
  546. 			Update();
  547. 			ind=0;
  548. 			REP(i,s)if(tempTaken[i])present[ind++]=i;
  549. 		}
  550. 		lim=5;
  551. 		memset(tempTaken2,0,sizeof(tempTaken2));
  552. 		REP(i,lim){
  553. 			if(ind<=6)break;
  554. 			int a1 = rand()%ind,a2=a1,a3=a1,a4=a1,a5=a1,a6=a1;
  555. 			while(a2==a1)a2=rand()%ind;
  556. 			while(a3==a1||a3==a2)a3=rand()%ind;
  557. 			while(a4==a1||a4==a2||a4==a3)a4=rand()%ind;
  558. 			while(a5==a1||a5==a2||a5==a3||a5==a4)a5=rand()%ind;
  559. 			while(a6==a1||a6==a2||a6==a3||a6==a4||a6==a5)a6=rand()%ind;
  560. 			a1 = present[a1];
  561. 			a2 = present[a2];
  562. 			a3 = present[a3];
  563. 			a4 = present[a4];
  564. 			a5 = present[a5];
  565. 			a6 = present[a6];
  566. 			discard(a1);discard(a2);discard(a3);discard(a4);discard(a5);discard(a6);
  567. 			doIter2();
  568. 			Update();
  569. 			ind=0;
  570. 			REP(i,s)if(tempTaken[i])present[ind++]=i;
  571. 		}
  572. 		lim=3;
  573. 		if(d<=100)lim=6;
  574. 		REP(i,lim){
  575. 			if(ind<=5)break;
  576. 			random_shuffle(present,present+ind);
  577. 			int tmp = rand()%ind;
  578. 			if(tmp<=2)tmp=3;
  579. 			REP(j,tmp)discard(present[j]);
  580. 			doIter();
  581. 			Update();
  582. 			ind=0;
  583. 			REP(i,s)if(tempTaken[i])present[ind++]=i;
  584. 		}
  585. 		if(d>100)break;
  586. 	}
  587.  
  588. 	/********************************** Output here *****************************************/
  589. 	int cnt=0;
  590. 	REP(i,s)if(taken[i])cnt++;
  591. 	putint(cnt);putchar(10);
  592. 	REP(i,s)if(taken[i]){
  593. 		putint(i);
  594. 		putchar(10);
  595. 	}
  596. 	fprintf(stderr,"%d\n",globalScore);
  597. 	flush_output();
  598. 	return 0;
  599. }
  600.

Comments