API tools faq
paste
cincout

С дист тур 4

cincout
Oct 7th, 2019
123
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.78 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 350;
  6. int a[N][N], b[N][N];
  7. int mn[N], sum[N];
  8.  
  9. pair<int, int> coord[N][N];
  10.  
  11. void fail() {
  12. cout << -1;
  13. exit(0);
  14. }
  15.  
  16. vector <pair<int, int>> pth;
  17.  
  18. void gen_path(int n, int m) {
  19. pth.clear();
  20. if (n % 2 == 0) {
  21. pth.push_back({1, 1});
  22. for (int i = 1; i <= n; ++i) {
  23. if (i % 2) {
  24. for (int j = 2; j <= m; ++j) {
  25. pth.push_back({i, j});
  26. }
  27. }
  28. else {
  29. for (int j = m; j >= 2; --j) {
  30. pth.push_back({i, j});
  31. }
  32. }
  33. }
  34. for (int i = n; i > 1; --i) {
  35. pth.push_back({i, 1});
  36. }
  37. return;
  38. }
  39. pth.push_back({1, m});
  40. for (int i = m; i >= 1; --i) {
  41. if (i % 2 == 0) {
  42. for (int j = 2; j <= n; ++j) {
  43. pth.push_back({j, i});
  44. }
  45. }
  46. else {
  47. for (int j = n; j >= 2; --j) {
  48. pth.push_back({j, i});
  49. }
  50. }
  51. }
  52. for (int i = 1; i < m; ++i) {
  53. pth.push_back({1, i});
  54. }
  55. }
  56.  
  57. void print(int i, int j, bool flag = false) {
  58. for (int k = 0; k < pth.size(); ++k) {
  59. if (pth[k] != make_pair(i, j)) continue;
  60. for (int id = k, j = 0; j < pth.size(); j++, id = (id + 1) % pth.size()) {
  61. if (flag) {
  62. int x = pth[id].first;
  63. int y = pth[id].second;
  64. cout << coord[x][y].first << " " << coord[x][y].second << "\n";
  65. }
  66. else {
  67. cout << pth[id].first << " " << pth[id].second << "\n";
  68. }
  69. }
  70. }
  71. }
  72.  
  73. void solve() {
  74. int n, m;
  75. cin >> n >> m;
  76.  
  77. if (n % 2 && m % 2) fail();
  78.  
  79. gen_path(n, m);
  80.  
  81. for (int i = 1; i <= n; ++i) {
  82. for (int j = 1; j <= m; ++j) {
  83. cin >> a[i][j];
  84. }
  85. }
  86.  
  87. if (n % 2 == 0) {
  88. for (int i = 1; i <= n; ++i) {
  89. int cur = 0, s = 0;
  90. if (i % 2) {
  91. for (int j = 2; j <= m; ++j) {
  92. cur += a[i][j];
  93. if (cur < 0) s = max(s, abs(cur));
  94. }
  95. }
  96. else {
  97. for (int j = m; j >= 2; --j) {
  98. cur += a[i][j];
  99. if (cur < 0) s = max(s, abs(cur));
  100. }
  101. }
  102. sum[i] = cur;
  103. mn[i] = s;
  104. }
  105. int cur = 0, s = 0;
  106. for (int i = n; i >= 1; --i) {
  107. cur += a[i][1];
  108. if (cur < 0) s = max(s, abs(cur));
  109. }
  110. mn[n + 1] = s;
  111. sum[n + 1] = cur;
  112.  
  113. for (int i = 1; i <= n; ++i) {
  114. for (int j = 2; j <= m; ++j) {
  115. int kek = 0;
  116. bool ok = 1;
  117. if (i % 2) {
  118. for (int id = j; id <= m; ++id) {
  119. kek += a[i][id];
  120. if (kek < 0) ok = 0;
  121. }
  122. }
  123. else {
  124. for (int id = j; id >= 2; --id) {
  125. kek += a[i][id];
  126. if (kek < 0) ok = 0;
  127. }
  128. }
  129. if (!ok) continue;
  130. for (int k = i + 1; k <= n + 1; ++k) {
  131. if (kek < mn[k]) {
  132. ok = 0;
  133. break;
  134. }
  135. kek += sum[k];
  136. }
  137. for (int k = 1; k < i; ++k) {
  138. if (kek < mn[k]) {
  139. ok = 0;
  140. break;
  141. }
  142. kek += sum[k];
  143. }
  144. if (i % 2) {
  145. for (int id = 2; id < j; ++id) {
  146. kek += a[i][id];
  147. if (kek < 0) ok = 0;
  148. }
  149. }
  150. else {
  151. for (int id = m; id > j; --id) {
  152. kek += a[i][id];
  153. if (kek < 0) ok = 0;
  154. }
  155. }
  156. if (!ok) continue;
  157. print(i, j);
  158. return;
  159. }
  160.  
  161. for (int i = 1; i <= n; ++i) {
  162. int kek = 0;
  163. bool ok = 1;
  164. for (int j = i; j >= 1; --j) {
  165. kek += a[j][1];
  166. if (kek < 0) ok = 0;
  167. }
  168. for (int k = 1; k <= n; ++k) {
  169. if (kek < mn[k]) {
  170. ok = 0;
  171. break;
  172. }
  173. kek += sum[k];
  174. }
  175. for (int j = n; j > i; --j) {
  176. kek += a[j][1];
  177. if (kek < 0) ok = 0;
  178. }
  179. if (!ok) continue;
  180. print(i, 1);
  181. return;
  182. }
  183. }
  184. cout << -1;
  185. return;
  186. }
  187.  
  188. pair<int, int> d = {1, 1};
  189. for (int i = m; i >= 1; --i) {
  190. for (int j = 1; j <= n; ++j) {
  191. coord[d.first][d.second] = {j, i};
  192. b[d.first][d.second] = a[j][i];
  193. d.second++;
  194. if (d.second == n + 1) {
  195. d.second = 1;
  196. d.first++;
  197. }
  198. }
  199. }
  200.  
  201. swap(n, m);
  202. for (int i = 1; i <= n; ++i) {
  203. for (int j = 1; j <= m; ++j) {
  204. a[i][j] = b[i][j];
  205. }
  206. }
  207. gen_path(n, m);
  208.  
  209.  
  210. if (n % 2 == 0) {
  211. for (int i = 1; i <= n; ++i) {
  212. int cur = 0, s = 0;
  213. if (i % 2) {
  214. for (int j = 2; j <= m; ++j) {
  215. cur += a[i][j];
  216. if (cur < 0) s = max(s, abs(cur));
  217. }
  218. }
  219. else {
  220. for (int j = m; j >= 2; --j) {
  221. cur += a[i][j];
  222. if (cur < 0) s = max(s, abs(cur));
  223. }
  224. }
  225. sum[i] = cur;
  226. mn[i] = s;
  227. }
  228. int cur = 0, s = 0;
  229. for (int i = n; i >= 1; --i) {
  230. cur += a[i][1];
  231. if (cur < 0) s = max(s, abs(cur));
  232. }
  233. mn[n + 1] = s;
  234. sum[n + 1] = cur;
  235.  
  236. for (int i = 1; i <= n; ++i) {
  237. for (int j = 2; j <= m; ++j) {
  238. int kek = 0;
  239. bool ok = 1;
  240. if (i % 2) {
  241. for (int id = j; id <= m; ++id) {
  242. kek += a[i][id];
  243. if (kek < 0) ok = 0;
  244. }
  245. }
  246. else {
  247. for (int id = j; id >= 2; --id) {
  248. kek += a[i][id];
  249. if (kek < 0) ok = 0;
  250. }
  251. }
  252. if (!ok) continue;
  253. for (int k = i + 1; k <= n + 1; ++k) {
  254. if (kek < mn[k]) {
  255. ok = 0;
  256. break;
  257. }
  258. kek += sum[k];
  259. }
  260. for (int k = 1; k < i; ++k) {
  261. if (kek < mn[k]) {
  262. ok = 0;
  263. break;
  264. }
  265. kek += sum[k];
  266. }
  267. if (i % 2) {
  268. for (int id = 2; id < j; ++id) {
  269. kek += a[i][id];
  270. if (kek < 0) ok = 0;
  271. }
  272. }
  273. else {
  274. for (int id = m; id > j; --id) {
  275. kek += a[i][id];
  276. if (kek < 0) ok = 0;
  277. }
  278. }
  279. if (!ok) continue;
  280. print(i, j, 1);
  281. return;
  282. }
  283.  
  284. for (int i = 1; i <= n; ++i) {
  285. int kek = 0;
  286. bool ok = 1;
  287. for (int j = i; j >= 1; --j) {
  288. kek += a[j][1];
  289. if (kek < 0) ok = 0;
  290. }
  291. for (int k = 1; k <= n; ++k) {
  292. if (kek < mn[k]) {
  293. ok = 0;
  294. break;
  295. }
  296. kek += sum[k];
  297. }
  298. for (int j = n; j > i; --j) {
  299. kek += a[j][1];
  300. if (kek < 0) ok = 0;
  301. }
  302. if (!ok) continue;
  303. print(i, 1, 1);
  304. return;
  305. }
  306. }
  307. cout << -1;
  308. return;
  309. }
  310. }
  311.  
  312. int main() {
  313. ios::sync_with_stdio(0); cin.tie(0);
  314. cout.setf(ios::fixed); cout.precision(20);
  315. solve();
  316. return 0;
  317. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!