oj.uz

Submission #569782

# Submission time Handle Problem Language Result Execution time Memory
569782 2022-05-27T19:08:32 Z mat_v Furniture (JOI20_furniture) C++14
100 / 100
 335 ms 17820 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m;
int mat[1005][1005];
int kol[2005];
bool dobar[1005][1005][2];

void radi(int x, int y, int idx){
    if(x <= 0 && y <= 0 && x > n || y > m)return;
    if(!dobar[x][y][idx])return;
    if(idx == 0){
        bool sta = 0;
        if(!mat[x+1][y])sta |= dobar[x+1][y][0];
        if(!mat[x][y+1])sta |= dobar[x][y+1][0];
        if(!sta){
            if(dobar[x][y][idx^1])kol[x+y]--;
            dobar[x][y][idx] = 0;
            radi(x-1,y,0);
            radi(x,y-1,0);
        }
    }
    else{
        bool sta = 0;
        if(!mat[x-1][y])sta |= dobar[x-1][y][1];
        if(!mat[x][y-1])sta |= dobar[x][y-1][1];
        if(!sta){
            if(dobar[x][y][idx^1])kol[x+y]--;
            dobar[x][y][idx] = 0;
            radi(x+1,y,1);
            radi(x,y+1,1);
        }
    }
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    ff(i,1,n){
        ff(j,1,m)cin >> mat[i][j];
    }
    dobar[n][m][0] = 1;
    dobar[1][1][1] = 1;
    fb(i,n,1){
        fb(j,m,1){

            if(i == n && j == m || mat[i][j] == 1)continue;
            if(!mat[i+1][j])dobar[i][j][0] |= dobar[i+1][j][0];
            if(!mat[i][j+1])dobar[i][j][0] |= dobar[i][j+1][0];
        }
    }
    ff(i,1,n){
        ff(j,1,m){
            if(i == 1 && j == 1 || mat[i][j] == 1)continue;
            if(!mat[i-1][j])dobar[i][j][1] |= dobar[i-1][j][1];
            if(!mat[i][j-1])dobar[i][j][1] |= dobar[i][j-1][1];
        }
    }
    ff(i,1,n){
        ff(j,1,m){
            if(dobar[i][j][0] && dobar[i][j][1])kol[i+j]++;
        }
    }
    //cout << kol[4] << "\n";
   // cout << dobar[2][2][0] << " " << dobar[2][2][1] << "\n";
    int q;
    cin >> q;
    while(q--){
        int x,y;
        cin >> x >> y;
        bool mogu = 0;
        if(!dobar[x][y][0] || !dobar[x][y][1])mogu = 1;
        if(kol[x+y] > 1)mogu = 1;
        cout << mogu << "\n";
        if(mogu){
            if(dobar[x][y][0] && dobar[x][y][1])kol[x+y]--;
            dobar[x][y][0] = dobar[x][y][1] = 0;
            radi(x-1,y,0);
            radi(x,y-1,0);
            radi(x,y+1,1);
            radi(x+1,y,1);
        }
    }


    return 0;
}

Compilation message

furniture.cpp: In function 'void radi(int, int, int)':
furniture.cpp:29:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |     if(x <= 0 && y <= 0 && x > n || y > m)return;
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~
furniture.cpp: In function 'int main()':
furniture.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
furniture.cpp:61:5: note: in expansion of macro 'ff'
   61 |     ff(i,1,n){
      |     ^~
furniture.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
furniture.cpp:62:9: note: in expansion of macro 'ff'
   62 |         ff(j,1,m)cin >> mat[i][j];
      |         ^~
furniture.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
furniture.cpp:66:5: note: in expansion of macro 'fb'
   66 |     fb(i,n,1){
      |     ^~
furniture.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
furniture.cpp:67:9: note: in expansion of macro 'fb'
   67 |         fb(j,m,1){
      |         ^~
furniture.cpp:69:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |             if(i == n && j == m || mat[i][j] == 1)continue;
      |                ~~~~~~~^~~~~~~~~
furniture.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
furniture.cpp:74:5: note: in expansion of macro 'ff'
   74 |     ff(i,1,n){
      |     ^~
furniture.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
furniture.cpp:75:9: note: in expansion of macro 'ff'
   75 |         ff(j,1,m){
      |         ^~
furniture.cpp:76:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   76 |             if(i == 1 && j == 1 || mat[i][j] == 1)continue;
      |                ~~~~~~~^~~~~~~~~
furniture.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
furniture.cpp:81:5: note: in expansion of macro 'ff'
   81 |     ff(i,1,n){
      |     ^~
furniture.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
furniture.cpp:82:9: note: in expansion of macro 'ff'
   82 |         ff(j,1,m){
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 828 KB Output is correct
4 Correct 3 ms 976 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 4 ms 992 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 828 KB Output is correct
4 Correct 3 ms 976 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 4 ms 992 KB Output is correct
10 Correct 10 ms 972 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 161 ms 10848 KB Output is correct
13 Correct 57 ms 7924 KB Output is correct
14 Correct 279 ms 15416 KB Output is correct
15 Correct 276 ms 15644 KB Output is correct
16 Correct 291 ms 16616 KB Output is correct
17 Correct 310 ms 17500 KB Output is correct
18 Correct 307 ms 16912 KB Output is correct
19 Correct 305 ms 17740 KB Output is correct
20 Correct 295 ms 17740 KB Output is correct
21 Correct 335 ms 17820 KB Output is correct