Submission #1033496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033496		vjudge1	Furniture (JOI20_furniture)	C++17	5 / 100	5077 ms	14936 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
bitset<1010> reach[1010], open[1010];
int n,m;
bool check(){    
    reach[0][1]=1;
    for(int i=1;i<=m;i++) {
        reach[i]=reach[i-1]&open[i];
        for(int j=2;j<=n;j++)
            if(open[i][j]&&reach[i][j-1])
                reach[i][j]=1;
    }
    return reach[m][n];
}
int X[1000100],Y[1000100],fail[1000100];
int state;
void moveto(int nxt){
    while(state<nxt)
        state++,open[X[state]][Y[state]]=0;
    while(state>nxt)
        open[X[state]][Y[state]]=1,state--;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int q;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            open[j][i]=!x;
        }
    reach[0][1]=1;
    for(int i=1;i<=m;i++) {
        reach[i]=reach[i-1]&open[i];
        for(int j=2;j<=n;j++)
            if(open[i][j]&&reach[i][j-1])
                reach[i][j]=1;
    }
    cin>>q;
    for(int i=1;i<=q;i++)
        cin>>Y[i]>>X[i];
    int prv=0;
    while(moveto(q),!check()) {
        int l=prv+1,r=q;
        int res=0;
        while(l<=r){
            int mid=l+r>>1;
            moveto(mid);
            if(check())
                l=mid+1;
            else r=mid-1,res=mid;
        }
        moveto(res);
        open[X[res]][Y[res]]=1;
        fail[res]=1;
        prv=res;
    }
    for(int i=1;i<=q;i++)
        cout<<!fail[i]<<'\n';
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:49:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             int mid=l+r>>1;
      |                     ~^~

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