Submission #293775

#TimeUsernameProblemLanguageResultExecution timeMemory
293775BTheroFurniture (JOI20_furniture)C++17
100 / 100
3991 ms7628 KiB
// chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << x << endl; using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAXN = (int)1e3 + 5; const int MAXM = (int)1e6 + 9; int dp[MAXN][MAXN]; char s[MAXN][MAXN]; int n, m, q; vector<array<int, 3>> todo; bool go(int diag, int l, int r) { if (l > r) { return 0; } if (diag == 0) { return 1; } todo.pb({diag, l, r}); int nl = l, nr = r - 1; int x = l - 1, y = diag - l; if (x >= 0 && dp[x][y + 1] == 0) { nl--; } x = r, y = diag - r - 1; if (y >= 0 && dp[x + 1][y] == 0) { nr++; } return go(diag - 1, nl, nr); } void solve() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { scanf(" %c", &s[i][j]); } } scanf("%d", &q); for (int x = n - 1; ~x; --x) { for (int y = m - 1; ~y; --y) { if (x == n - 1 && y == m - 1) { dp[x][y] = 1; continue; } dp[x][y] = 0; if (s[x][y] != '1') { dp[x][y] |= dp[x + 1][y]; dp[x][y] |= dp[x][y + 1]; } } } for (int i = 1; i <= q; ++i) { int x, y; scanf("%d %d", &x, &y); --x; --y; if (dp[x][y] == 0) { s[x][y] = '1'; printf("1\n"); continue; } todo.clear(); if (go(x + y, x, x)) { printf("0\n"); } else { printf("1\n"); s[x][y] = '1'; for (auto &[diag, l, r] : todo) { for (int i = l; i <= r; ++i) { dp[i][diag - i] = 0; } } } } } int main() { int tt = 1; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

furniture.cpp: In function 'void solve()':
furniture.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:57:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |       scanf(" %c", &s[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
furniture.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...