Submission #1402790

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

double get_time() {
  unsigned long long a, d;
  __asm__ volatile("rdtsc" : "=a"(a), "=d"(d));
  return (d << 32 | a) / 2500000.0;
}

unsigned get_random() {
  static unsigned y = 2463534242;
  return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
}

const int n = 30;

int solve(int a[n][n]) {
  int res = 0;
  while (true) {
    int v0, v1, v2 = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (v2 < a[i][j]) {
          v2 = a[i][j];
          v0 = i;
          v1 = j;
        }
      }
    }
    if (v2 == 0) break;
    res += v2;
    vector<tuple<int, int>> queue;
    queue.push_back(make_tuple(v0, v1));
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    while (true) {
      int x = get<0>(queue.back());
      int y = get<1>(queue.back());
      int nx, ny, v = 0;
      for (int i = 0; i < 4; ++i) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx < 0 || n <= tx) continue;
        if (ty < 0 || n <= ty) continue;
        if (a[x][y] > a[tx][ty] && a[tx][ty] > v) {
          v = a[tx][ty];
          nx = tx;
          ny = ty;
        }
      }
      if (v == 0) break;
      queue.push_back(make_tuple(nx, ny));
    }
    int fx = get<0>(queue.front());
    int fy = get<1>(queue.front());
    int s = queue.size();
    while (a[fx][fy] > 0) {
      --a[fx][fy];
      printf("%d %d\n", fx + 1, fy + 1);
      for (int i = 1; i < s; ++i) {
        int px = get<0>(queue[i - 1]);
        int py = get<1>(queue[i - 1]);
        int x = get<0>(queue[i]);
        int y = get<1>(queue[i]);
        if (a[x][y] == 0 || a[px][py] > a[x][y]) break;
        --a[x][y];
        printf("%d %d\n", x + 1, y + 1);
      }
    }
  }
  return res;
}

int main() {
  if (true) {
    int a[n][n];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cin >> a[i][j];
      }
    }
    solve(a);
  } else {
  }
}

Submission Info

Judge Result