Submission #994851

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N = 333;

vector <int> g[N * N];
bool alive_a[N * N], alive_b[N * N];
int pa[N * N], pb[N * N], was[N * N];
int it;

bool dfs(int v) {
  was[v] = it;
  for (int j = 0; j < (int) g[v].size(); j++) {
    int u = g[v][j];
    if (alive_b[u] && pb[u] == -1) {
      pa[v] = u;
      pb[u] = v;
      return true;
    }
  }
  for (int j = 0; j < (int) g[v].size(); j++) {
    int u = g[v][j];
    if (alive_b[u] && was[pb[u]] != it) {
      if (dfs(pb[u])) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
  }
  return false;
}

bool dfs_finish(int v, int finish) {
  if (pa[v] == finish) {
    return true;
  }
  int old = pa[v];
  pa[v] = -1;
  pb[old] = -1;
  it++;
  if (dfs(pb[finish])) {
    pa[v] = finish;
    pb[finish] = v;
    return true;
  }
  pa[v] = old;
  pb[old] = v;
  return false;
}

int what[N * N];
int U[N], D[N], L[N], R[N];
int empty[N][N];
int first_L[N], first_R[N], first_U[N], first_D[N];
int cell_L[N], cell_R[N], cell_U[N], cell_D[N];

int n;

void take_cell(int i, int j) {
  alive_b[i * n + j] = false;
  empty[i][j] = 0;
  if (cell_L[i] == j) {
    while (cell_L[i] < n && !empty[i][cell_L[i]]) {
      cell_L[i]++;
    }
  }
  if (cell_R[i] == j) {
    while (cell_R[i] >= 0 && !empty[i][cell_R[i]]) {
      cell_R[i]--;
    }
  }
  if (cell_U[j] == i) {
    while (cell_U[j] < n && !empty[cell_U[j]][j]) {
      cell_U[j]++;
    }
  }
  if (cell_D[j] == i) {
    while (cell_D[j] >= 0 && !empty[cell_D[j]][j]) {
      cell_D[j]--;
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", U + i);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", D + i);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", L + i);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", R + i);
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    first_L[i] = cnt;
    for (int j = 0; j < L[i]; j++) {
      what[cnt++] = i;
    }
    first_R[i] = cnt;
    for (int j = 0; j < R[i]; j++) {
      what[cnt++] = i;
    }
  }
  for (int i = 0; i < n; i++) {
    first_U[i] = cnt;
    for (int j = 0; j < U[i]; j++) {
      what[cnt++] = ~i;
    }
    first_D[i] = cnt;
    for (int j = 0; j < D[i]; j++) {
      what[cnt++] = ~i;
    }
  }
  for (int k = 0; k < cnt; k++) {
    if (what[k] >= 0) {
      for (int j = 0; j < n; j++) {
        g[k].push_back(what[k] * n + j);
      }
    } else {
      for (int i = 0; i < n; i++) {
        g[k].push_back(i * n + (~what[k]));
      }
    }
  }
  for (int i = 0; i < cnt; i++) {
    pa[i] = -1;
    pb[i] = -1;
    was[i] = -1;
  }
  for (int i = 0; i < n * n; i++) {
    alive_a[i] = true;
    alive_b[i] = true;
  }
  for (int i = 0; i < cnt; i++) {
    it++;
    if (!dfs(i)) {
      puts("NO");
      return 0;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      empty[i][j] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    cell_L[i] = 0;
    cell_R[i] = n - 1;
    cell_U[i] = 0;
    cell_D[i] = n - 1;
  }
  for (int iter = 0; iter < n * n; iter++) {
    bool found = false;
    for (int i = 0; i < n; i++) {
      if (L[i] > 0) {
        int j = cell_L[i];
        if (dfs_finish(first_L[i], i * n + j)) {
          printf("L%d\n", i + 1);
          L[i]--;
          alive_a[first_L[i]] = false;
          first_L[i]++;
          take_cell(i, j);
          found = true;
          break;
        }
      }
    }
    if (found) {
      continue;
    }
    for (int i = 0; i < n; i++) {
      if (R[i] > 0) {
        int j = cell_R[i];
        if (dfs_finish(first_R[i], i * n + j)) {
          printf("R%d\n", i + 1);
          R[i]--;
          alive_a[first_R[i]] = false;
          first_R[i]++;
          take_cell(i, j);
          found = true;
          break;
        }
      }
    }
    if (found) {
      continue;
    }
    for (int j = 0; j < n; j++) {
      if (U[j] > 0) {
        int i = cell_U[j];
        if (dfs_finish(first_U[j], i * n + j)) {
          printf("U%d\n", j + 1);
          U[j]--;
          alive_a[first_U[j]] = false;
          first_U[j]++;
          take_cell(i, j);
          found = true;
          break;
        }
      }
    }
    if (found) {
      continue;
    }
    for (int j = 0; j < n; j++) {
      if (D[j] > 0) {
        int i = cell_D[j];
        if (dfs_finish(first_D[j], i * n + j)) {
          printf("D%d\n", j + 1);
          D[j]--;
          alive_a[first_D[j]] = false;
          first_D[j]++;
          take_cell(i, j);
          found = true;
          break;
        }
      }
    }
    assert(found);
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:89:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", U + i);
                       ^
./Main.cpp:92:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", D + i);
                       ^
./Main.cpp:95:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", L + i);
                       ^
./Main.cpp:98:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", R + i);
                       ^

Judge Result