fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define PI acos(-1)
  5. #define hell 1000000007
  6. #define HELL 998244353
  7. #define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  8. #define fix(n) cout << fixed << setprecision(n)
  9. #define mset(a,n) memset(a,n,sizeof a)
  10. #define rep(i,a,b) for (__typeof((b)) i=(a);i<(b);i++)
  11. #define repp(i,a,b,p) for(__typeof((b)) i=(a);i<(b);i+=p)
  12. #define ren(i,a,b) for(__typeof((a)) i=(a);i>=(b);i--)
  13. #define renn(i,a,b,p) for(__typeof((a) i=(a);i>=(b);i-=p)
  14. #define ADD(a,b,c) ((a)%c+(b)%c)%c
  15. #define SUB(a,b,c) ((a)%c-(b)%c+c)%c
  16. #define MUL(a,b,c) (((a)%c)*((b)%c))%c
  17. #define lbd lower_bound
  18. #define ubd upper_bound
  19. #define ll long long
  20. #define ld long double
  21. #define pb push_back
  22. #define fi first
  23. #define se second
  24. #define vll vector<ll>
  25. #define pll pair<ll,ll>
  26. #define vpll vector<pll>
  27. #define all(v) (v).begin(), (v).end()
  28. #define sz(x) (ll)x.size()
  29. #define endl "\n"
  30. #define out(n) cout<<n<<" "
  31. #define outl(n) cout<<n<<endl
  32. #define line cout<<endl
  33. #define bug(n) {outl(n);return;}
  34. #define N 2505
  35. ll n,f=0;
  36. string s,t,ans="ZZZZZZZZZZZZZZZZ";
  37. set<string> m;
  38. vector<string> a;
  39. bool check(ll i, char b[][4], ll j){
  40. 	if(j>=4){
  41. 		rep(k,0,4){
  42. 			if(b[k][j-4]=='-'||b[k][j-4]==a[i][k]){}
  43. 			else return 0;
  44. 		}
  45. 	}else{
  46. 		rep(k,0,4){
  47. 			if(b[j][k]=='-'||b[j][k]==a[i][k]){}
  48. 			else return 0;
  49. 		}
  50. 	}
  51. 	return 1;
  52. }
  53. void fun(ll i, char b[][4], vll v){
  54. 	if(i==n){
  55. 		string res;
  56. 		rep(i,0,4){
  57. 			rep(j,0,4)res+=b[i][j];
  58. 		}
  59. 		ans=min(ans,res);
  60. 		f=1;
  61. 		return;
  62. 	}
  63. 	rep(j,0,8){
  64. 		if(!v[j]){
  65. 			if(check(i,b,j)){
  66. 				char temp[4][4];
  67. 				rep(i,0,4){
  68. 					rep(j,0,4)temp[i][j]=b[i][j];
  69. 				}
  70. 				if(j>=4){
  71. 					rep(k,0,4)b[k][j-4]=a[i][k];
  72. 				}else{
  73. 					rep(k,0,4)b[j][k]=a[i][k];
  74. 				}
  75. 				v[j]=1;
  76. 				fun(i+1,b,v);
  77. 				v[j]=0;
  78. 				rep(i,0,4){
  79. 					rep(j,0,4)b[i][j]=temp[i][j];
  80. 				}
  81. 			}
  82. 		}
  83. 	}
  84. }
  85. bool check2(vector<string> a, vector<string> b){
  86. 	vector<string> c;
  87. 	rep(j,0,4){
  88. 		string s;
  89. 		rep(i,0,4)s+=a[i][j];
  90. 		c.pb(s);
  91. 	}
  92. 	ll C=0;
  93. 	for(auto i:b){
  94. 		if(find(all(c),i)!=c.end())C++;
  95. 		else{
  96. 			reverse(all(i));
  97. 			if(find(all(c),i)!=c.end())C++;
  98. 		}
  99. 	}
  100. 	return C==sz(b);
  101. }
  102. void fun2(ll i, vll v){
  103. 	if(sz(v)==4){
  104. 		do{
  105. 			vector<string> V;
  106. 			for(auto i:v)V.pb(a[i]);
  107. 			rep(k,0,16){
  108. 				rep(i,0,4){
  109. 					if((k&(1ll<<i)))reverse(all(V[i]));
  110. 				}
  111. 				vector<string> W;
  112. 				rep(i,0,n){
  113. 					if(find(all(v),i)==v.end())W.pb(a[i]);
  114. 				}
  115. 				if(check2(V,W)){
  116. 					string res;
  117. 					for(auto i:V)res+=i;
  118. 					ans=min(ans,res);
  119. 					res="";
  120. 					rep(j,0,4){
  121. 						rep(i,0,4)res+=V[i][j];
  122. 					}
  123. 					ans=min(ans,res);
  124. 				}
  125. 				rep(i,0,4){
  126. 					if((k&(1ll<<i)))reverse(all(V[i]));
  127. 				}
  128. 			}
  129. 		}while(next_permutation(all(v)));
  130. 		return;
  131. 	}
  132. 	if(i==n)return;
  133. 	fun2(i+1,v);
  134. 	v.pb(i);
  135. 	fun2(i+1,v);
  136. }
  137. void solve(){
  138. 	cin>>n;
  139. 	m.clear();
  140. 	a.clear();
  141. 	ans="ZZZZZZZZZZZZZZZZ";
  142. 	rep(i,0,n){
  143. 		cin>>s;
  144. 		t=s;
  145. 		reverse(all(t));
  146. 		if(m.count(s)||m.count(t)){}
  147. 		else m.insert(s);
  148. 	}
  149. 	for(auto i:m)a.pb(i);
  150. 	n=sz(a);
  151. 	f=0;
  152. 	if(n>=7){
  153. 		vll v;
  154. 		fun2(0,v);
  155. 	}else if(n==6){
  156.  
  157. 	}else{
  158. 		char b[4][4];
  159. 		rep(i,0,4){
  160. 			rep(j,0,4)b[i][j]='-';
  161. 		}
  162. 		vll v(8,0);
  163. 		fun(0,b,v);
  164. 	}
  165. 	if(!f)ans="gridsnotpossible";
  166. 	rep(i,0,4){
  167. 		rep(j,0,4)cout<<ans[4*i+j];
  168. 		line;
  169. 	}
  170. 	line;
  171. }
  172. void prep(){
  173.  
  174. }
  175. int main(){
  176.     io;
  177.     ll t=1;
  178.     cin>>t;
  179.     prep();
  180.     fix(12);
  181.     while(t--)
  182.         solve();
  183.     return 0;
  184. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
----
----
----
----
https://ideone.com/pMuKnu
language:
C++ (gcc 8.3)
created:
4 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!