Submission #298766

#	Time	Username	Problem	Language	Result	Execution time	Memory
298766		Pro_ktmr	Furniture (JOI20_furniture)	C++14	100 / 100	545 ms	24952 KiB

furniture

#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int H, W;
int C[1002][1002] = {};
int Q;
int Y[1000000], X[1000000];

queue<pair<int,int>> que;

void fill2(int i, int j, int dy, int dx){
    if(i < 0 || H+2 <= i || j < 0 || W+2 <= j) return;
    if(C[i][j] == 2) return;
    C[i][j] = 2;
    fill2(i+dy, j+dx, dy, dx);
    if(C[i+1][j-1] == 1) que.push({i+1, j-1});
}

void fill3(int i, int j, int dy, int dx){
    if(i < 0 || H+2 <= i || j < 0 || W+2 <= j) return;
    if(C[i][j] == 3) return;
    C[i][j] = 3;
    fill3(i+dy, j+dx, dy, dx);
    if(C[i-1][j+1] == 1) que.push({i-1, j+1});
}

bool solved[1002][1002] = {};
void solve(){
    while(!que.empty()){
        int i = que.front().first;
        int j = que.front().second;
        que.pop();
        if(solved[i][j]) continue;
        if(C[i-1][j+1] == 2 && C[i+1][j-1] == 3) return;
        C[i][j] = 1;
        if(C[i-1][j+1] == 2){
            fill2(i, j, -1, 0);
            C[i][j] = 1;
            fill2(i, j, 0, 1);
            solved[i][j] = true;
        }
        if(C[i+1][j-1] == 3){
            fill3(i, j, 1, 0);
            C[i][j] = 1;
            fill3(i, j, 0, -1);
            solved[i][j] = true;
        }
    }
}

void print(){
    /*for(int i=0; i<H+2; i++){
        for(int j=0; j<W+2; j++){
            printf("%d", C[i][j]);
        }
        printf("\n");
    }*/
}

signed main(){
    scanf("%d%d", &H, &W);
    rep(i, H){
        rep(j, W){
            scanf("%d", &C[i+1][j+1]);
        }
    }
    scanf("%d", &Q);
    rep(i, Q){
        scanf("%d%d", &Y[i], &X[i]);
    }

    for(int j=2; j<W+2; j++) C[0][j] = 2;
    for(int i=0; i<H; i++) C[i][W+1] = 2;
    for(int j=0; j<W; j++) C[H+1][j] = 3;
    for(int i=2; i<H+2; i++) C[i][0] = 3;
    print();

    for(int i=1; i<H+1; i++){
        for(int j=1; j<W+1; j++){
            if(C[i][j] == 1){
                que.push({i,j});
            }
        }
    }
    solve();
    print();

    rep(i, Q){
        que.push({Y[i],X[i]});
        solve();
        printf("%d\n", C[Y[i]][X[i]] != 0);
    }
    print();
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
furniture.cpp:76:5: note: in expansion of macro 'rep'
   76 |     rep(i, H){
      |     ^~~
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
furniture.cpp:77:9: note: in expansion of macro 'rep'
   77 |         rep(j, W){
      |         ^~~
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
furniture.cpp:82:5: note: in expansion of macro 'rep'
   82 |     rep(i, Q){
      |     ^~~
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
furniture.cpp:102:5: note: in expansion of macro 'rep'
  102 |     rep(i, Q){
      |     ^~~
furniture.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("%d%d", &H, &W);
      |     ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |             scanf("%d", &C[i+1][j+1]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
furniture.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
furniture.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         scanf("%d%d", &Y[i], &X[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95