Submission #1287191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287191		StefanSebez	Furniture (JOI20_furniture)	C++20	100 / 100	294 ms	14356 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=1010;
int a[N][N],n,m;
int b[2][N][N];
void Update(int type,int x,int y){
    if(b[type][x][y]==0) return;
    vector<pair<int,int>>upd;
    if(type==1){
        for(int i=x-1;i>=1&&b[type][i][y];i--){
            b[type][i][y]=0;
            b[type][i+1][y-1]=1;
            if(a[i+1][y-1]) upd.pb({i+1,y-1});
        }
        for(int j=y+1;j<=m&&b[type][x][j];j++){
            b[type][x][j]=0;
            b[type][x+1][j-1]=1;
            if(a[x+1][j-1]) upd.pb({x+1,j-1});
        }
        b[type][x][y]=0;
        b[type][x+1][y-1]=1;
        if(a[x+1][y-1]) upd.pb({x+1,y-1});
        for(auto [x,y]:upd) Update(type,x,y);
    }
    else{
        for(int i=x+1;i<=n&&b[type][i][y];i++){
            b[type][i][y]=0;
            b[type][i-1][y+1]=1;
            if(a[i-1][y+1]) upd.pb({i-1,y+1});
        }
        for(int j=y-1;j>=1&&b[type][x][j];j--){
            b[type][x][j]=0;
            b[type][x-1][j+1]=1;
            if(a[x-1][j+1]) upd.pb({x-1,j+1});
        }
        b[type][x][y]=0;
        b[type][x-1][y+1]=1;
        if(a[x-1][y+1]) upd.pb({x-1,y+1});
        for(auto [x,y]:upd) Update(type,x,y);
    }
}
int main(){
    scanf("%i%i",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%i",&a[i][j]);
        }
    }
    for(int j=1;j<=m;j++) b[0][n][j]=b[1][1][j]=1;
    for(int i=1;i<=n;i++) b[0][i][1]=b[1][i][m]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]&&b[0][i][j]) Update(0,i,j);
            if(a[i][j]&&b[1][i][j]) Update(1,i,j);
        }
    }
    int q;scanf("%i",&q);
    while(q--){
        int x,y;scanf("%i%i",&x,&y);
        if(a[x][y]==1||(b[0][x][y]&&b[1][x][y])){printf("0\n");continue;}
        a[x][y]=1;
        Update(0,x,y);
        Update(1,x,y);
        printf("%i\n",a[x][y]);
    }
    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
furniture.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             scanf("%i",&a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~
furniture.cpp:63:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     int q;scanf("%i",&q);
      |           ~~~~~^~~~~~~~~
furniture.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         int x,y;scanf("%i%i",&x,&y);
      |                 ~~~~~^~~~~~~~~~~~~~

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