oj.uz

Submission #1033496

# Submission time Handle Problem Language Result Execution time Memory
1033496 2024-07-25T00:08:06 Z vjudge1 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 14936 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 11 ms 344 KB Output is correct
4 Correct 36 ms 652 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 40 ms 600 KB Output is correct
7 Correct 33 ms 600 KB Output is correct
8 Correct 34 ms 600 KB Output is correct
9 Correct 37 ms 600 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 11 ms 344 KB Output is correct
4 Correct 36 ms 652 KB Output is correct
5 Correct 39 ms 600 KB Output is correct
6 Correct 40 ms 600 KB Output is correct
7 Correct 33 ms 600 KB Output is correct
8 Correct 34 ms 600 KB Output is correct
9 Correct 37 ms 600 KB Output is correct
10 Correct 1177 ms 1404 KB Output is correct
11 Correct 36 ms 600 KB Output is correct
12 Correct 4024 ms 7504 KB Output is correct
13 Correct 34 ms 2388 KB Output is correct
14 Execution timed out 5077 ms 14936 KB Time limit exceeded
15 Halted 0 ms 0 KB -