Submission #669946

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <functional>
#include <numeric>
#include <limits>
#include <tuple>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

namespace HK {
const int MAX_LR = 32 * 32 * 105;

int L, R;
vector<int> adj[MAX_LR];
bool vis[MAX_LR], usd[MAX_LR];
int lev[MAX_LR + 1], mat[MAX_LR];

bool augment(int l) {
  if (l == L) return true;
  if (vis[l]) return false;
  vis[l] = true;
  rep (i, adj[l].size()) {
    int r = adj[l][i], l2 = mat[r];
    if (lev[l2] > lev[l] && augment(l2)) {
      mat[r] = l;
      return true;
    }
  }
  return false;
}

int bipartite_matching() {
  fill(mat, mat + R, L);
  memset(usd, 0, sizeof(bool) * L);
  bool update;
  do {
    fill(lev, lev + L + 1, -1);
    lev[L] = R;
    queue<int> que;
    rep (l, L) if (!usd[l]) {
      que.push(l);
      lev[l] = 0;
    }
    while (!que.empty()) {
      int l = que.front();
      que.pop();
      rep (i, adj[l].size()) {
        int r = adj[l][i], l2 = mat[r];
        if (lev[l2] < 0) {
          lev[l2] = lev[l] + 1;
          que.push(l2);
        }
      }
    }

    memset(vis, 0, sizeof(bool) * L);
    update = false;
    rep (l, L) if (!usd[l] && augment(l)) usd[l] = update = true;
  } while (update);

  return count(usd, usd + L, true);
}
}  // namespace HK

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int N = 30;
int A[40][40];

int vbase[40][40];
int vid(int x, int y, int a) {
  return vbase[y][x] + (a - 1);
}

const int MAX_P = 100010;

int P, pid[MAX_P];
vector<vector<tuple<int, int, int>>> paths;
bool pdone[MAX_P];
vector<int> pfwd[MAX_P], pbwd[MAX_P];

int pcrrdeg[MAX_P], crrA[40][40];
int num_pdone = 0;

void output_path(int p) {
  assert(pcrrdeg[p] == 0);

  for (auto t : paths[p]) {
    int x = get<0>(t), y = get<1>(t);
    printf("%d %d\n", y, x);
    --crrA[y][x];
  }

  for (int q : pbwd[p]) --pcrrdeg[q];
  pdone[p] = true;
  ++num_pdone;
}

void output_path_recursive(int p) {
  if (pdone[p]) return;
  pdone[p] = true;
  for (auto q : pfwd[p]) output_path_recursive(q);
  output_path(p);
}

int match(std::function<bool(int, int, int, int)> f) {
  int s = 0;
  for (int y = 1; y <= N; ++y) {
    for (int x = 1; x <= N; ++x) {
      vbase[y][x] = s;
      s += A[y][x];
    }
  }
  HK::L = HK::R = s;
  rep (l, HK::L) HK::adj[l].clear();

  for (int y = 1; y <= N; ++y) {
    for (int x = 1; x <= N; ++x) {
      for (int a = 2; a <= A[y][x]; ++a) {
        rep (d, 4) {
          int tx = x + dx[d], ty = y + dy[d];
          if (a - 1 <= A[ty][tx] && f(x, y, tx, ty)) {
            HK::adj[vid(x, y, a)].push_back(vid(tx, ty, a - 1));
          }
        }
      }
    }
  }

  return HK::bipartite_matching();
}

int mdist(int x, int y, int tx, int ty) {
  return abs(x - tx) + abs(y - ty);
}

int main(int argc, char **argv) {
  if (argc != 1) N = atoi(argv[1]);
  for (int y = 1; y <= N; ++y) {
    for (int x = 1; x <= N; ++x) {
      scanf("%d", &A[y][x]);
    }
  }

  //
  // Bipartite matching
  //
  match([&](int x, int y, int tx, int ty) -> bool {
      return x + y < tx + ty;
    });

  //
  // Decompose
  //
  memset(pid, -1, sizeof(pid));
  for (int a = 1; a <= 110; ++a) {
    for (int y = 1; y <= N; ++y) {
      for (int x = 1; x <= N; ++x) {
        if (a > A[y][x]) continue;

        int &p = pid[vid(x, y, a)];
        if (p == -1) {
          p = paths.size();
          paths.emplace_back();
        }
        paths[p].emplace_back(x, y, a);
        pid[HK::mat[vid(x, y, a)]] = p;  // parent
      }
    }
  }
  P = paths.size();
  for (auto &p : paths) reverse(all(p));
  fprintf(stderr, "Num of paths: %d\n", P);
  fprintf(stderr, "Point: %d\n", 100000 - P);

  //
  // Graph
  //
  rep (p, P) {
    for (auto t : paths[p]) {
      int x, y, a;
      tie(x, y, a) = t;
      if (a + 1 <= A[y][x]) {
        int q = pid[vid(x, y, a + 1)];
        assert(p != q);
        pfwd[p].pb(q);
        pbwd[q].pb(p);
      }
    }
  }
  rep (p, P) pcrrdeg[p] = pfwd[p].size();

  //
  // Greedy reconnection
  //
  int num_happy = 0;
  for (int y = 1; y <= N; ++y) for (int x = 1; x <= N; ++x) crrA[y][x] = A[y][x];

  while (num_pdone < P) {
    // Starting position
    int x, y;
    {
      vector<tuple<double, int, int, int>> ps;
      for (int y = 1; y <= N; ++y) {
        for (int x = 1; x <= N; ++x) {
          int a = crrA[y][x], p = pid[vid(x, y, a)];
          if (paths[p][0] != make_tuple(x, y, a) || pcrrdeg[p] != 0) continue;
          ps.emplace_back(a - x, rand(), x, y);
        }
      }
      assert(!ps.empty());
      sort(ps.rbegin(), ps.rend());
      tie(x, y) = make_pair(get<2>(ps[0]), get<3>(ps[0]));
    }
    int a = crrA[y][x];

    // Greedy
    for (;;) {
      int p = pid[vid(x, y, a)];
      assert(paths[p][0] == make_tuple(x, y, a));
      output_path(p);
      {
        auto t = paths[p].back();
        x = get<0>(t);
        y = get<1>(t);
        a = get<2>(t);
      }
      if (a == 1) break;

      vector<int> ds(4);
      iota(all(ds), 0);
      random_shuffle(all(ds));
      rep (i, 4) {
        int d = ds[i];
        int tx = x + dx[d], ty = y + dy[d], ta = a - 1;
        if (ta != crrA[ty][tx]) continue;
        int tp = pid[vid(tx, ty, ta)];
        if (paths[tp][0] != make_tuple(tx, ty, ta)) continue;
        if (pdone[tp] || pcrrdeg[tp] > 0) continue;

        tie(x, y, a) = make_tuple(tx, ty, ta);
        goto found;
      }
      break;
   found:
      ++num_happy;
    }
  }

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:162:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &A[y][x]);
                            ^

Judge Result