oj.uz

Submission #623023

# Submission time Handle Problem Language Result Execution time Memory
623023 2022-08-05T05:28:49 Z Mahdi Furniture (JOI20_furniture) C++17
100 / 100
 1075 ms 52980 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e3+5;
int n, m, q;
bool a[N][N], b[N][N], x[N][N], y[N][N], c[N][N];

bool add(int i, int j){
    if(!x[i+1][j-1] && !y[i-1][j+1])
        return 0;
    set<pii>s, t;
    vector<pii>v;
    v.push_back({i, j});
    if(a[i][j]){
        a[i][j]=0;
        for(int k=0;k<v.size();++k){
            i=v[k].F, j=v[k].S;
            if(x[i][j])
                s.insert({-i, j});
            if(y[i][j])
                t.insert({i, -j});
            if(a[i+1][j] && !a[i+1][j-1]){
                v.push_back({i+1, j});
                a[i+1][j]=0;
            }
            if(a[i][j+1] && !a[i-1][j+1]){
                v.push_back({i, j+1});
                a[i][j+1]=0;
            }
        }
    }
    v.resize(1);
    if(b[v[0].F][v[0].S]){
        b[v[0].F][v[0].S]=0;
        for(int k=0;k<v.size();++k){
            i=v[k].F, j=v[k].S;
            if(x[i][j])
                s.insert({-i, j});
            if(y[i][j])
                t.insert({i, -j});
            if(b[i-1][j] && !b[i-1][j+1]){
                v.push_back({i-1, j});
                b[i-1][j]=0;
            }
            if(b[i][j-1] && !b[i+1][j-1]){
                v.push_back({i, j-1});
                b[i][j-1]=0;
            }
        }
    }
    while(!s.empty()){
        i=-s.begin()->F;
        j=s.begin()->S;
        s.erase(s.begin());
        if(!x[i+1][j] && !x[i][j-1] && (!a[i][j] || !b[i][j])){
            x[i][j]=0;
            if(x[i-1][j])
                s.insert({-i+1, j});
            if(x[i][j+1])
                s.insert({-i, j+1});
        }
    }
    while(!t.empty()){
        i=t.begin()->F;
        j=-t.begin()->S;
        t.erase(t.begin());
        if(!y[i-1][j] && !y[i][j+1] && (!a[i][j] || !b[i][j])){
            y[i][j]=0;
            if(y[i+1][j])
                t.insert({i+1, -j});
            if(y[i][j-1])
                t.insert({i, -j+1});
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            a[i][j]=b[i][j]=x[i][j]=y[i][j]=1;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>c[i][j];
            if(c[i][j])
                add(i, j);
        }
    }
    cin>>q;
    while(q--){
        int i, j;
        cin>>i>>j;
        cout<<add(i, j)<<'\n';
    }
}

Compilation message

furniture.cpp: In function 'bool add(int, int)':
furniture.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int k=0;k<v.size();++k){
      |                     ~^~~~~~~~~
furniture.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int k=0;k<v.size();++k){
      |                     ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 4 ms 848 KB Output is correct
3 Correct 5 ms 916 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 10 ms 984 KB Output is correct
6 Correct 10 ms 996 KB Output is correct
7 Correct 8 ms 1108 KB Output is correct
8 Correct 7 ms 1236 KB Output is correct
9 Correct 8 ms 980 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 4 ms 848 KB Output is correct
3 Correct 5 ms 916 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 10 ms 984 KB Output is correct
6 Correct 10 ms 996 KB Output is correct
7 Correct 8 ms 1108 KB Output is correct
8 Correct 7 ms 1236 KB Output is correct
9 Correct 8 ms 980 KB Output is correct
10 Correct 37 ms 1268 KB Output is correct
11 Correct 7 ms 776 KB Output is correct
12 Correct 687 ms 13512 KB Output is correct
13 Correct 181 ms 8008 KB Output is correct
14 Correct 818 ms 14844 KB Output is correct
15 Correct 840 ms 15468 KB Output is correct
16 Correct 717 ms 16008 KB Output is correct
17 Correct 791 ms 16784 KB Output is correct
18 Correct 785 ms 16364 KB Output is correct
19 Correct 1020 ms 28836 KB Output is correct
20 Correct 1075 ms 52980 KB Output is correct
21 Correct 967 ms 29332 KB Output is correct