5
Your rating: None Average: 5 (1 vote)

CodeChef submission 184252 (C++ 4.3.2)

CodeChef submission 184252 (C++ 4.3.2) plaintext list. Status: AC, problem M3, contest FEB10. By codegambler (codegambler), 2010-02-09 14:03:32.
  1. //=====================================================================================
  2. //	Filename:  M3.cpp
  3. //	Description: 
  4. //	Created:  02/01/2010 05:04:19 PM
  5. //	Author:  pankaj kumar, pankaj4u4m@gmail.com 
  6. //=====================================================================================
  7. #include <cassert>//c headers in c++
  8. #include <cctype>
  9. #include <cfloat>
  10. #include <cmath>
  11. #include <cstdarg>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <cstring>
  15. #include <algorithm>//c++ headers
  16. #include <bitset>
  17. #include <complex>
  18. #include <deque>
  19. #include <functional>
  20. #include <iostream>
  21. #include <iomanip>
  22. #include <iterator>
  23. #include <limits>
  24. #include <list>
  25. #include <map>
  26. #include <memory>
  27. #include <new>
  28. #include <numeric>
  29. #include <queue>
  30. #include <set>
  31. #include <sstream>
  32. #include <stack>
  33. #include <string>
  34. #include <utility>
  35. #include <valarray>
  36. #include <vector>
  37. using namespace std;
  38.  
  39. /*START OF TEMPLATE:BY_PANKAJ_CODEGAMBLER*/
  40. #define INF 		2000000000//::INF
  41. #define VAR(x,a) 	__typeof(a) x=(a)//::VAR(
  42. #define FE(it,c) 	for(VAR(it,(c).begin());it!=(c).end();++it)//::FE(
  43. #define FOR(i,a,b)  	for(int i=(int)(a),_b=(int)(b) ; i < _b;++i)//::FOR(
  44. #define FORR(i,a,b) 	for(int i=(a),_b=(b);i>=_b;--i)//::FORR(
  45. #define	REP(i,n)    	FOR(i,0,n)//::REP(
  46. #define ALL(c) 		(c).begin(),(c).end()//::ALL(
  47. #define SZ(c) 		(int)(c).size()//::SZ(
  48. #define PB      push_back//::PB
  49. #define PF      push_front//::PF
  50. #define V(x)    vector< x >//::V(
  51. #define VI      V(int)//::VI
  52. #define VVI     V(VI)//::VII
  53. #define VS      V(string)//::VS
  54. #define PI     pair< int,int >//::PI
  55. #define MP      make_pair//::MP
  56. #define pi      3.14159265358979323846//::pi
  57.  
  58. const double eps=1e-11;//::eps
  59. typedef long long LL;//::LL
  60. typedef unsigned long long ULL;//::ULL
  61. typedef long double LD;//::LD
  62.  
  63. /* Input Output Function */
  64. #define BUFSIZE (1<<16)
  65. char BUF[BUFSIZE+1], *inp=BUF;
  66. #define DIG(a) (((a)>='0')&&((a)<='9'))//::DIG(
  67. #define getChar(t) {if(!*inp){BUF[fread(BUF,1,BUFSIZE,stdin)]=0;inp=BUF;}t=*inp++;}//::getChar(
  68. #define getInt(j) {int t;char sign;do{sign = t;getChar(t);}while(!DIG(t));j=t-'0'; getChar(t);while(DIG(t)){j=10*j+(t-'0');getChar(t);}if(sign == '-') j = -j;}//::getInt(
  69.  
  70.  
  71. /* Only for Debugging */
  72. #define out(__debug) cout << #__debug<< "=" <<__debug << endl;//::out(
  73. template<class T> void outC(T A)//::outContainer
  74. {cout<<"{"; FE(it,A)cout << *it << " " ;cout<<"}"<<endl;}
  75. template<class T> void outA(T A[],int n)//::outArray
  76. { cout<<"{"; for (int i=0;i<n;i++) cout<<A[i]<<" "; cout<<"}"<<endl;}
  77. template<class T> void outV(vector<T> A,int n=-1)//::outVector
  78. { if (n<0) n=SZ(A); cout<<"{"; for (int i=0;i<n;i++) cout<<A[i]<<" "; cout<<"}"<<endl;}
  79. template<class T> static void split(const string &s, vector<T> &out)//::split(
  80. {istringstream in(s);out.clear();copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));}
  81. /*END TEMPLATE:BY_PANKAJ_CODEGAMBLER*/
  82. int ans[150];
  83. int n;
  84. //int tog_sz=0;
  85. int a[150][150];
  86. char res[150];
  87. int counter = 0;
  88. int col[150];
  89. int chk  =0;
  90. void solve(){
  91. 	memset(ans, 0, sizeof ans);
  92. 	REP(i, n)REP(j, n){
  93. 		if( a[i][j]  == 1) ans[i]++;
  94. 	}
  95. 	int ansm = *max_element(ans, ans+n);
  96. 	//int nby2 = (n-1)/2;
  97. 	REP(row, n){
  98. 		chk = 0;
  99. 		memset(col, 0, sizeof col);
  100. 		REP(i, n){
  101. 			if( a[i][row] == 1){col[i]++;chk = 1;} 
  102. 		}
  103. 		counter = 0;
  104. 		REP(i, n){
  105. 			if( a[row][i] == 1||a[row][i] == 2) counter ++;
  106. 		}
  107. 		if( counter >= n/2 ){
  108. 			int fl = 0;
  109. 			if( counter == n/2) {
  110. 				REP(i, n){
  111. 					int cnt =0 ;
  112. 					REP(j, n){
  113. 						if( a[i][j] == 1|| a[i][j] == 2) cnt++;
  114. 					}
  115. 				//	out(cnt);
  116. 					if( cnt < n/2){fl =1 ;break;}
  117. 				}
  118. 			}
  119. 			if( fl == 0 && counter >= ansm){
  120. 			//now matter
  121. 				VI maxele;
  122. 				REP(i, n){
  123. 					if( ans[i] == ansm ) maxele.PB(i);
  124. 				}
  125. 				int sz = SZ(maxele);
  126. 				int f = 0;
  127. 				REP(i, sz)FOR(j, i+1, sz){
  128. 					if( a[maxele[i]][maxele[j]] == 2) f=1;
  129. 				}
  130. 				if( f== 1) ansm ++;
  131. 				if( counter >= ansm) res[row] = '1';
  132. 			}
  133. 		}
  134. 	}
  135. }
  136. int main()
  137. {
  138. //	freopen("M3.cppin","r",stdin);
  139. 	fgets(BUF, BUFSIZE,  stdin);
  140. 	int T;
  141. 	//scanf("%d", &T);
  142. 	getInt(T);
  143. 	while(T--){
  144. 		getInt(n);
  145. //	memset(a, 0, sizeof a);
  146. 		memset(res, '0', sizeof res); 
  147. 		REP(i, n)REP(j, n)
  148. 			getInt(a[i][j]);
  149. 			//	scanf("%d", &a[i][j]);
  150. 		//input over;
  151. 		solve();
  152. 		res[n] = 0;
  153. 		printf("%s\n", res);
  154. 	}
  155. 	return 0;
  156. }
  157.  
  158.  
  159.

Comments