fork download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<vector>
  4. #include<cstring>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef unsigned int ui;
  11. typedef pair<int,int> pii;
  12.  
  13. #define MAXN 1000005
  14.  
  15. int n, m, cnt[4][4], id[128], GS[4][MAXN], GC[4][MAXN], IS[4][MAXN], IC[4][MAXN], colp[MAXN], rowp[MAXN], vis[4][MAXN], code[4][4], memC[MAXN], pi[3*MAXN], done[4][MAXN];
  16.  
  17. string small, large, cycle, text;
  18.  
  19. int findShift(string &s, string &t) {
  20.     if(s.size() != t.size()) return -1;
  21. 	text = s + "#" + t + t;
  22. 	int sz = s.size();
  23.  
  24. 	int l = text.length();
  25. 	pi[0] = 0;
  26. 	for (int i = 1; i < l; i++) {
  27. 		int j = pi[i-1];
  28. 		while(j > 0 && text[i] != text[j]) {
  29. 			j = pi[j-1];
  30. 		}
  31. 		if(text[i] == text[j]) {
  32. 			j++;
  33. 		}
  34. 		pi[i] = j;
  35. 	}
  36.  
  37. 	for(int i = 2*sz; i < l; i++) {
  38. 		if(pi[i] == sz) {
  39. 			return i-2*sz;
  40. 		}
  41. 	}
  42. 	return -1;
  43. }
  44.  
  45. int main() {
  46. 	freopen("input.in", "r", stdin);
  47.  
  48. 	int L = id['L'] = 0;
  49. 	int T = id['T'] = 1;
  50. 	int R = id['R'] = 2;
  51. 	int B = id['B'] = 3;
  52.  
  53. 	scanf("%d %d\n", &n, &m);
  54. 	for(int i = 0; i < n+m; i++) {
  55. 		char a, b; int p, q;
  56. 		scanf("%c %c %d %d\n", &a, &b, &p, &q);
  57. 		a = id[a];
  58. 		b = id[b];
  59. 		cnt[a][b]++;
  60. 		cnt[b][a]++;
  61. 		GS[a][p] = b;
  62. 		GC[a][p] = q;
  63. 		GS[b][q] = a;
  64. 		GC[b][q] = p;
  65. 	}
  66.  
  67. 	if((cnt[T][B] && cnt[L][R]) || (cnt[L][T] != cnt[B][R])) {
  68. 		printf("No solution\n");
  69. 		return 0;
  70. 	}
  71.  
  72. 	int smallPtr[4];
  73. 	int d = min(cnt[L][T], cnt[L][B]);
  74. 	for(int x = 1; x <= cnt[L][T]; x++) {
  75. 		IS[L][x] = T;
  76. 		IS[T][x] = L;
  77. 		IC[L][x] = x;
  78. 		IC[T][x] = x;
  79. 		smallPtr[L] = 1;
  80. 	}
  81. 	for(int x = 1; x <= cnt[T][R]; x++) {
  82. 		IS[T][m-x+1] = R;
  83. 		IS[R][x] = T;
  84. 		IC[T][m-x+1] = x;
  85. 		IC[R][x] = m-x+1;
  86. 		smallPtr[T] = m-d+1;
  87. 	}
  88. 	for(int x = 1; x <= cnt[R][B]; x++) {
  89. 		IS[R][n-x+1] = B;
  90. 		IS[B][m-x+1] = R;
  91. 		IC[R][n-x+1] = m-x+1;
  92. 		IC[B][m-x+1] = n-x+1;
  93. 		smallPtr[R] = n-d+1;
  94. 	}
  95. 	for(int x = 1; x <= cnt[B][L]; x++) {
  96. 		IS[B][x] = L;
  97. 		IS[L][n-x+1] = B;
  98. 		IC[B][x] = n-x+1;
  99. 		IC[L][n-x+1] = x;
  100. 		smallPtr[B] = 1;
  101. 	}
  102. 	for(int x = cnt[L][T]+1, y = cnt[T][R]+1; x <= cnt[L][T]+cnt[L][R]; x++, y++) {
  103. 		IS[L][x] = R;
  104. 		IS[R][y] = L;
  105. 		IC[L][x] = y;
  106. 		IC[R][y] = x;
  107. 	}
  108. 	for(int x = cnt[L][T]+1, y = cnt[L][B]+1; x <= cnt[L][T]+cnt[T][B]; x++, y++) {
  109. 		IS[T][x] = B;
  110. 		IS[B][y] = T;
  111. 		IC[T][x] = y;
  112. 		IC[B][y] = x;
  113. 	}
  114.  
  115. 	char cd = 'A';
  116. 	for(int i = 0; i < 4; i++) {
  117. 		for(int j = 0; j < 4; j++) {
  118. 			code[i][j] = cd++;
  119. 		}
  120. 	}
  121.  
  122. 	int startS = -1, startC = d+1;
  123. 	if(cnt[L][R]) {
  124. 		startS = L;
  125. 	} else if(cnt[T][B]) {
  126. 		startS = T;
  127. 	} else if(cnt[L][T] != cnt[L][B]) {
  128. 		startS = L;
  129. 	}
  130. 	if(startS != -1) {
  131. 		int currS = startS, currC = startC;
  132. 		while(1) {
  133. 			int nextS = IS[currS][currC];
  134. 			int nextC = IC[currS][currC];
  135. 			large += code[currS][nextS];
  136. 			currS = (nextS+2)%4;
  137. 			currC = nextC;
  138. 			if(currS==startS && currC==startC) {
  139. 				break;
  140. 			}
  141. 		}
  142. 	}
  143.  
  144. 	if(startS == -1) {
  145. 		startS = 0;
  146. 	}
  147. 	for(int i = 0; i < 4; i++) {
  148. 		int nextS = (startS+1)%4;
  149. 		small += code[startS][nextS];
  150. 		startS = (nextS+2)%4;
  151. 	}
  152.  
  153. 	if(d > 0) {
  154. 		int smallCnt = 0;
  155. 		for(int x = 1; x <= (startS%2==0?n:m); x++) {
  156. 			if(!vis[startS][x] && code[startS][GS[startS][x]] == small[0]) {
  157. 				cycle = string();
  158. 				int currS = startS, currC = x;
  159. 				for(int i = 0; ; i++) {
  160. 					vis[currS][currC] = true;
  161. 					memC[i] = currC;
  162. 					int nextS = GS[currS][currC];
  163. 					int nextC = GC[currS][currC];
  164. 					cycle += code[currS][nextS];
  165. 					currS = (nextS+2)%4;
  166. 					currC = nextC;
  167. 					if(currS==startS && currC==x) {
  168. 						break;
  169. 					}
  170. 				}
  171.  
  172. 				if(cycle.length() == small.length()) {
  173. 					int p = findShift(small, cycle);
  174. 					if(p != -1) {
  175. 						smallCnt++;
  176.  
  177. 						currS = startS;
  178. 						currC = smallPtr[startS]++;
  179. 						for(int j = p, k = 0; k < 4; j=(j+1)%4, k++) {
  180. 							if(currS%2==0) {
  181. 								rowp[currC] = memC[j];
  182. 							} else {
  183. 								colp[currC] = memC[j];
  184. 							}
  185. 							done[currS][memC[j]] = 1;
  186. 							int nextS = IS[currS][currC];
  187. 							int nextC = IC[currS][currC];
  188. 							currS = (nextS+2)%4;
  189. 							currC = nextC;
  190. 						}
  191. 					}
  192. 				}
  193. 			}
  194. 		}
  195.  
  196. 		if(smallCnt != d) {
  197. 			printf("No solution\n");
  198. 			return 0;
  199. 		}
  200. 	}
  201.  
  202. 	d = large.size()?(n+m-4*d)/large.size():0;
  203. 	if(d > 0) {
  204. 		int largeCnt = 0;
  205. 		memset(vis, 0, sizeof(vis));
  206. 		for(int x = 1; x <= (startS%2==0?n:m); x++) {
  207. 			if(!vis[startS][x] && !done[startS][x] && code[startS][GS[startS][x]] == large[0]) {
  208. 				cycle = string();
  209. 				int currS = startS, currC = x;
  210. 				for(int i = 0; ; i++) {
  211. 					vis[currS][currC] = true;
  212. 					memC[i] = currC;
  213. 					int nextS = GS[currS][currC];
  214. 					int nextC = GC[currS][currC];
  215. 					cycle += code[currS][nextS];
  216. 					currS = (nextS+2)%4;
  217. 					currC = nextC;
  218. 					if(currS==startS && currC==x) {
  219. 						break;
  220. 					}
  221. 				}
  222.  
  223. 				if(cycle.length() == large.length()) {
  224. 					int p = findShift(large, cycle);
  225. 					if(p != -1) {
  226. 						largeCnt++;
  227.  
  228. 						currS = startS;
  229. 						currC = startC++;
  230. 						int sz = large.size();
  231. 						for(int j = p, k = 0; k < sz; j=(j+1)%sz, k++) {
  232. 							if(currS%2==0) {
  233. 								rowp[currC] = memC[j];
  234. 							} else {
  235. 								colp[currC] = memC[j];
  236. 							}
  237. 							int nextS = IS[currS][currC];
  238. 							int nextC = IC[currS][currC];
  239. 							currS = (nextS+2)%4;
  240. 							currC = nextC;
  241. 						}
  242. 					}
  243. 				}
  244. 			}
  245. 		}
  246.  
  247. 		if(largeCnt != d) {
  248. 			printf("No solution\n");
  249. 			return 0;
  250. 		}
  251. 	}
  252.  
  253. 	for(int i = 1; i <= n; i++) {
  254. 		printf("%d ", rowp[i]);
  255. 	}
  256. 	printf("\n");
  257. 	for(int i = 1; i <= m; i++) {
  258. 		printf("%d ", colp[i]);
  259. 	}
  260. 	printf("\n");
  261. }
  262.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bm0GQP
language:
C++ (gcc 8.3)
created:
11 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!