oj.uz

Submission #857014

# Submission time Handle Problem Language Result Execution time Memory
857014 2023-10-05T08:24:56 Z mgl_diamond Furniture (JOI20_furniture) C++17
100 / 100
 285 ms 21432 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4648 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 4 ms 6492 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4648 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 4 ms 6492 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 8 ms 4700 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 137 ms 14536 KB Output is correct
13 Correct 51 ms 11580 KB Output is correct
14 Correct 242 ms 19140 KB Output is correct
15 Correct 259 ms 19520 KB Output is correct
16 Correct 262 ms 20288 KB Output is correct
17 Correct 284 ms 21112 KB Output is correct
18 Correct 276 ms 20564 KB Output is correct
19 Correct 276 ms 21328 KB Output is correct
20 Correct 279 ms 21432 KB Output is correct
21 Correct 285 ms 21428 KB Output is correct