Submission #516305

#TimeUsernameProblemLanguageResultExecution timeMemory
516305qwerasdfzxclFurniture (JOI20_furniture)C++14
100 / 100
606 ms23844 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; int a[1010][1010], dp1[1010][1010], dp2[1010][1010], cnt[2020]; void debug(int n, int m){ printf("DEBUG\n"); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++) printf("%d ", dp1[i][j]); printf("\n"); } printf("\n"); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++) printf("%d ", dp2[i][j]); printf("\n"); } printf("\n"); } int main(){ int n, m; scanf("%d %d", &n, &m); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++) scanf("%d", a[i]+j); } for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ dp1[i][j] = dp1[i][j-1] | dp1[i-1][j]; if (a[i][j]) dp1[i][j] = 0; dp1[1][1] = 1; } } for (int i=n;i;i--){ for (int j=m;j;j--){ dp2[i][j] = dp2[i][j+1] | dp2[i+1][j]; if (a[i][j]) dp2[i][j] = 0; dp2[n][m] = 1; } } for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++) if (dp1[i][j] && dp2[i][j]) cnt[i+j]++; } //debug(n, m); int q; scanf("%d", &q); while(q--){ int x, y; scanf("%d %d", &x, &y); if (cnt[x+y]==1 && dp1[x][y] && dp2[x][y]) {printf("0\n"); continue;} printf("1\n"); a[x][y] = 1; queue<pair<int, int>> q; q.emplace(x, y); while(!q.empty()){ auto p = q.front(); q.pop(); if (!dp1[p.first][p.second]) continue; if (!a[p.first][p.second] && (dp1[p.first-1][p.second] || dp1[p.first][p.second-1])) continue; dp1[p.first][p.second] = 0; if (dp2[p.first][p.second]) cnt[p.first+p.second]--; if (p.first+1<=n) q.emplace(p.first+1, p.second); if (p.second+1<=m) q.emplace(p.first, p.second+1); } q.emplace(x, y); while(!q.empty()){ auto p = q.front(); q.pop(); if (!dp2[p.first][p.second]) continue; if (!a[p.first][p.second] && (dp2[p.first+1][p.second] || dp2[p.first][p.second+1])) continue; dp2[p.first][p.second] = 0; if (dp1[p.first][p.second]) cnt[p.first+p.second]--; if (p.first-1>0) q.emplace(p.first-1, p.second); if (p.second-1>0) q.emplace(p.first, p.second-1); } //debug(n, m); } return 0; }

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:26:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
      |                                ~~~~~^~~~~~~~~~~~~~
furniture.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
furniture.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...