Submission #684869

# Submission time Handle Problem Language Result Execution time Memory
684869 2023-01-22T17:52:46 Z alvingogo Furniture (JOI20_furniture) C++14
0 / 100
3 ms 340 KB
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int main(){
    AquA;
    int n,m;
    cin >> n >> m;
    vector<pair<int,int> > g;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int a;
            cin >> a;
            if(a){
                g.push_back({i,j});
            }
        }
    }
    int q;
    cin >> q;
    int u=g.size();
    for(int i=0;i<q;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        g.push_back({a,b});
    }
    vector<int> ans;
    const int dx[8]={1,1,1,0,-1,-1,-1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
    vector<vector<int> > ok(n,vector<int>(m)),d1(n,vector<int>(m)),d2=d1;
    vector<int> cnt(n+m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cnt[i+j]++;
            if(i+1<n){
                d1[i+1][j]++;
            }
            if(j+1<m){
                d1[i][j+1]++;
            }
            if(i-1>=0){
                d2[i-1][j]++;
            }
            if(j-1>=0){
                d2[i][j-1]++;
            }
        }
    }
    function<void(int,int)> del=[&](int x,int y){
        cout << x << " " << y << endl;
        cnt[x+y]--;
        ok[x][y]=1;
        if(x+1<n && !ok[x+1][y]){
            d1[x+1][y]--;
            if(d1[x+1][y]==0){
                del(x+1,y);
            }
        }
        if(y+1<m && !ok[x][y+1]){
            d1[x][y+1]--;
            if(d1[x][y+1]==0){
                del(x,y+1);
            }
        }
        if(y-1>=0 && !ok[x][y-1]){
            d2[x][y-1]--;
            if(d2[x][y-1]==0){
                del(x,y-1);
            }
        }
        if(x-1>=0 && !ok[x-1][y]){
            d2[x-1][y]--;
            if(d2[x-1][y]==0){
                del(x-1,y);
            }
        }
    };
    for(auto h:g){
        if(ok[h.fs][h.sc]){
            ans.push_back(1);
            continue;
        }
        if(cnt[h.fs+h.sc]>1){
            ans.push_back(1);
            del(h.fs,h.sc);
        }
        else{
            ans.push_back(0);
        }
    }
    for(int i=u;i<u+q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:34:15: warning: unused variable 'dx' [-Wunused-variable]
   34 |     const int dx[8]={1,1,1,0,-1,-1,-1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
      |               ^~
furniture.cpp:34:42: warning: unused variable 'dy' [-Wunused-variable]
   34 |     const int dx[8]={1,1,1,0,-1,-1,-1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
      |                                          ^~
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -