Submission #1212646

#TimeUsernameProblemLanguageResultExecution timeMemory
1212646cpdreamerFurniture (JOI20_furniture)C++20
0 / 100
428 ms589824 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1e12; typedef long long ll; const ll MOD=(ll) 998244353; #define P pair #define S second #define F first #define pb push_back #define V vector #define all(v) v.begin(),v.end() void file() { freopen("input.txt.txt", "r", stdin); freopen("output.txt.txt", "w", stdout); } set<P<int,int>>top,bot; P<int,int>prev_t[1001][1001],prev_b[1001][1001]; bool grid[1001][1001]; int m,n; void remove_top(P<int,int>p){ if(grid[p.F][p.S]){ top.erase(p); remove_top(prev_t[p.F][p.S]); return; } top.insert({p.F,p.S}); if (top.size()==m+n-1) { return; } if (!grid[p.F][p.S+1]) { remove_top({p.F,p.S+1}); } if(top.size()==m+n-1){ return; } if (!grid[p.F+1][p.S]) { remove_top({p.F+1,p.S}); } if(top.size()==m+n-1){ return; } grid[p.F][p.S]=true; remove_top({p.F,p.S}); } void remove_bot(P<int,int>p){ if(grid[p.F][p.S]){ bot.erase(p); remove_bot(prev_b[p.F][p.S]); return; } bot.insert({p.F,p.S}); if (bot.size()==m+n-1) { return; } if (!grid[p.F+1][p.S]) { remove_bot({p.F+1,p.S}); } if(bot.size()==m+n-1){ return; } if (!grid[p.F][p.S+1]) { remove_bot({p.F,p.S+1}); } if(bot.size()==m+n-1){ return; } grid[p.F][p.S]=true; remove_bot({p.F,p.S}); } void solve(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ grid[i][j]=false; } } for(int i=0;i<=n;i++){ grid[i][m]=true; } for(int i=0;i<=m;i++){ grid[n][i]=true; } for(int i=0;i<m;i++){ top.insert({0,i}); bot.insert({n-1,i}); } for(int i=0;i<n;i++) { top.insert({i,m-1}); bot.insert({i,0}); } auto it=top.begin(); for (int i=0;i<n+m-2;i++) { auto p=*it; it=next(it); prev_t[it->F][it->S]={p.F,p.S}; } it=bot.begin(); for (int i=0;i<n+m-2;i++) { auto p=*it; it =next(it); prev_t[it->F][it->S]={p.F,p.S}; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int x; cin>>x; if (x==0)continue; grid[i][j]=true; if(top.count({i,j})) { remove_top({i, j}); } if(bot.count({i,j})){ remove_bot({i,j}); } } } int q; cin>>q; while(q--){ int x,y; cin>>x>>y; x--,y--; if(top.count({x,y}) && bot.count({x,y})){ cout<<0<<endl; continue; } cout<<1<<endl; grid[x][y]=true; if(top.count({x,y})){ remove_top({x,y}); } if(bot.count({x,y})){ remove_bot({x,y}); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //file(); solve(); return 0; }

Compilation message (stderr)

furniture.cpp: In function 'void file()':
furniture.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("input.txt.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("output.txt.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...