fork(1) download 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <iomanip>
  13. #define dibs reserve
  14. #define OVER9000 1234567890
  15. #define patkan 9
  16. #define tisic 47
  17. #define soclose 1e-9
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define chocolate win
  20. #define ff first
  21. #define ss second
  22. #define abs(x) ((x < 0)?-(x):(x))
  23. // mylittledoge
  24. using namespace std;
  25.  
  26. struct cell {
  27. 	bool A;
  28. 	bool B[8];
  29. 	// N cells: U,L,D,R,UL,DL,DR,UR
  30. 	int diag[4];
  31. 	// N cells: minor,major diagonal start,end
  32.  
  33. 	cell() {
  34. 		A =true;
  35. 		for(int i =0; i < 4; i++) {
  36. 			B[i] =B[i+4] =false;
  37. 			diag[i] =0;}
  38. 		}
  39. };
  40.  
  41. int main() {
  42.     cin.sync_with_stdio(0);
  43.     cin.tie(0);
  44.     int N,a;
  45.     cin >> N;
  46.     vector< pair<int,int> > shops;
  47.     for(int i =0; i < N*N; i++) {
  48.     	cin >> a;
  49.     	if(a) shops.push_back(make_pair(i/N,i%N));}
  50.  
  51.     if(shops.size() > 2*N+patkan) {
  52.     	for(int i =0; i < N*N; i++)
  53.     		cout << "N" << ((i%N == N-1)?"\n":" ");
  54.     	return 0;}
  55.  
  56. 	vector< vector<cell> > A(N,vector<cell>(N));
  57.  
  58. 	for(int k =0; k < 4; k++) {
  59. 		ALL_THE(shops,it) ALL_THE(shops,jt) if(it->ff <= jt->ff && it->ss <= jt->ss) {
  60. 			if((jt->ff-it->ff+jt->ss-it->ss)%2) continue;
  61. 			// diagonal ends: "top" side?
  62. 			int x =it->ss+(jt->ff-it->ff+jt->ss-it->ss)/2;
  63. 			bool b =false;
  64. 			if(x <= jt->ss && x > it->ss) {
  65. 				A[it->ff][x].B[k] =true;
  66. 				b =true;
  67. 				A[it->ff][x].diag[k]++;}
  68. 			// diagonal ends: "right" side?
  69. 			int y =jt->ff-(jt->ff-it->ff+jt->ss-it->ss)/2;
  70. 			if(y < jt->ff && y >= it->ff) {
  71. 				A[y][jt->ss].B[(4+k-1)%4] =true;
  72. 				if(b) A[y][jt->ss].B[4+(4+k-1)%4] =true;
  73. 				A[y][jt->ss].diag[k]++;}
  74. 			}
  75.  
  76. 		// rotate -90°
  77. 		vector< vector<cell> > A0(N,vector<cell>(N));
  78. 		for(int i =0; i < N; i++) for(int j =0; j < N; j++)
  79. 			A0[j][N-1-i] =A[i][j];
  80. 		A =A0;
  81. 		ALL_THE(shops,it) {
  82. 			swap(it->ff,it->ss);
  83. 			it->ss =N-1-it->ss;}
  84. 		}
  85.  
  86. 	for(int k =0; k < 4; k++) {
  87. 		vector<bool> B(N,false);
  88.  
  89. 		for(int i =0; i < N; i++) {
  90. 			bool b =false;
  91. 			for(int j =0; j < N; j++) {
  92. 				b =b|A[i][j].B[(3+k)%4];
  93. 				B[j] =B[j]|A[i][j].B[4+(2+k)%4];
  94. 				if(j > 0) B[j] =B[j]|B[j-1];
  95.  
  96. 				A[i][j].A =A[i][j].A&(!(b|B[j]));}
  97. 			}
  98.  
  99. 		// diagonals
  100. 		for(int i =0; i < 2*N; i++) { // x+y
  101. 			int d =0;
  102. 			for(int j =-N; j <= N; j++) { // x-y
  103. 				if((i+j)%2) continue;
  104. 				int x =(i+j)/2, y =(i-j)/2;
  105. 				if(x < 0 || y < 0 || x >= N || y >= N) continue;
  106. 				d +=A[x][y].diag[k];
  107. 				if(d > 0) A[x][y].A =false;
  108. 				d -=A[x][y].diag[(2+k)%4];}
  109. 			}
  110.  
  111. 		// rotate -90°
  112. 		vector< vector<cell> > A0(N,vector<cell>(N));
  113. 		for(int i =0; i < N; i++) for(int j =0; j < N; j++)
  114. 			A0[j][N-1-i] =A[i][j];
  115. 		A =A0;}
  116.  
  117.    	for(int i =0; i < N*N; i++)
  118.    		cout << (A[i/N][i%N].A?"A":"N") << ((i%N == N-1)?"\n":" ");
  119.     return 0;}
  120.  
  121. // look at my code
  122. // my code is amazing
Success #stdin #stdout 0s 3484KB
comments (?)
stdin 
11
1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
stdout 
A A N A A A N N N A A
A N A A N N N N N N N
A N A N A N N N A A A
A N N A N N N N N N N
N N N N A N N A A A A
N N A N A N A N A A A
A N A N A N A A N A A
A N A N A N A A N A A
A N A N A N A A N A A
A N A N A N A A N A A
A N A N A N A A N A A
https://ideone.com/JRdXLm
OI 2014 1.
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!