Submission #857014

#	Time	Username	Problem	Language	Result	Execution time	Memory
857014		mgl_diamond	Furniture (JOI20_furniture)	C++17	100 / 100	285 ms	21432 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen("input.inp", "r")) {
    freopen("input.inp", "r", stdin);
    freopen("input.out", "w", stdout);
  }
}

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

int n, m, q, c[N][N], R[N][N], cnt[N + N];

int dp[N][N];

bool canTrau(int x, int y) {
  c[x][y] = 1;
  dp[1][1] = 1;
  foru(i, 1, n) {
    foru(j, 1, m) {
      if (i == 1 && j == 1) continue;
      if (c[i][j]) dp[i][j] = 0;
      else dp[i][j] = dp[i-1][j] | dp[i][j-1];
    }
  }
  c[x][y] = 0;

  return dp[n][m];
}

bool canSol(int x, int y) {
  if (!R[x][y]) return 1;
  return cnt[x+y] > 1;
}

bool bad(int x, int y) {
  if (x == 1 && y == 1) return 0;
  if (x == n && y == m) return 0;
  if (!R[x-1][y] && !R[x][y-1]) return 1;
  if (!R[x+1][y] && !R[x][y+1]) return 1;
  return 0;
}

void place(int ax, int ay) {
  c[ax][ay] = 1;
  if (R[ax][ay]) cnt[ax+ay] -= 1;
  R[ax][ay] = 0;

  queue<ii> qu;
  qu.push({ax, ay});

  while (!qu.empty()) {
    int x = qu.front().first, y = qu.front().second;
    qu.pop();

    foru(j, 0, 3) {
      int nx = x + dx[j], ny = y + dy[j];
      if (nx < 1 || ny < 1 || nx > n || ny > m || !R[nx][ny]) continue;
      if (bad(nx, ny)) {
//        if (ax == 2 && ay == 1) {
//          cout << nx << " " << ny << "\n";
//        }
        R[nx][ny] = 0;
        cnt[nx+ny] -= 1;
        qu.push({nx, ny});
      }
    }
  }
}



int main() {
  setIO();

  cin >> n >> m;
  foru(i, 1, n) foru(j, 1, m) cin >> c[i][j];

  R[1][1] = 1;
  foru(i, 1, n) {
    foru(j, 1, m) {
      if (i == 1 && j == 1) continue;
      if (c[i][j]) R[i][j] = 0;
      else R[i][j] = R[i-1][j] | R[i][j-1];
    }
  }

//  cout << c[15][16] << "\n";
//
//  cout << R[n][m] << "\n";

  ford(i, n, 1) {
    ford(j, m, 1) {
      if (i == n && j == m) continue;
      if (c[i][j]) R[i][j] = 0;
      else R[i][j] = R[i][j] & (R[i][j+1] | R[i+1][j]);
      if (R[i][j]) cnt[i+j] += 1;
    }
  }
  cnt[2] += 1;
  cnt[n+m] += 1;

//    foru(i, 1, n) {
//      foru(j, 1, m) {
//        cout << R[i][j] << " ";
//      }
//      cout << "\n";
//    }

//  cout << cnt[15+16] << "\n";
  int idx = 0;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
//    if (make_pair(x, y) == make_pair(1, 1)) continue;
//    if (make_pair(x, y) == make_pair(n, m)) continue;

//    ++idx;
//    if (canTrau(x, y) != canSol(x, y)) {
//      cout << idx << "\n";
//      cout << x << " " << y << "\n";
//      cout << canSol(x, y) << "\n";
//      cout << canTrau(x, y) << "\n";
//      break;
//      return 0;
//    }

    if (canSol(x, y)) {
      cout << 1 << "\n";
      place(x, y);
    }
    else {
      cout << 0 << "\n";
    }
//    foru(i, 1, n) {
//      foru(j, 1, m) {
//        cout << R[i][j] << " ";
//      }
//      cout << "\n";
//    }

//    if (canTrau(x, y) == canSol(x, y)) {
//      cout << x << " " << y << "\n";
//      cout << canSol(x, y) << "\n";
//      exit(0);
//    }
//    if (canTrau(x, y)) {
//      place(x, y);
//    }
  }
//  foru(i, 1, n) {
//    foru(j, 1, m) {
//      cout << R[i][j] << " ";
//    }
//    cout << "\n";
//  }

//  foru(i, 1, n) {
//    foru(j, 1, m) {
//      cout << R[i][j] << " ";
//    }
//    cout << "\n";
//  }
//
//  cout << canSol(15, 16) << "\n";
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:122:7: warning: unused variable 'idx' [-Wunused-variable]
  122 |   int idx = 0;
      |       ^~~
furniture.cpp: In function 'void setIO()':
furniture.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95