Submission #1310692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310692		putuputu	동굴 (IOI13_cave)	C++20	0 / 100	168 ms	600 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
    vector<int> s(n, 0);
    vector<int> use(n, 0);
    vector<int> dswitch(n, -1);
    vector<int> state(n, 0);
    for(int i=0; i<n; i++){
        vector<int>c;
        for(int j=0; j<n; j++){
            if(!use[j]){
                c.push_back(j);
            }
        }
        fill(s.begin(), s.end(), 0);
        for(int j=0; j<i; j++){
            s[dswitch[j]]=state[j];
        }
        int base=tryCombination(s.data());
        bool doorOpen=(base==-1 or base>i);
        if(doorOpen){
            for(int x : c){
                s[x]=1;
            }
        }
        int l=0, r=(int)c.size()-1;
        int find=-1;
        while(l<=r){
            int m=(l+r)/2;
            vector<int> s2=s;
            for(int j=l; j<=m; j++){
                s2[c[j]]^=1;
            }
            int res=tryCombination(s2.data());
            if(res==-1 or res>i){
                find=c[m];
                r=m-1;
            }else{
                l=m+1;
            }
        }
        if(find==-1){
            return;
        }
        vector<int> s3=s;
        s3[find]^=1;
        int res2=tryCombination(s3.data());
        int need;
        if(res2==-1 or res2>i){
            need=s3[find];
        }else{
            need=s[find];
        }
        use[find]=1;
        dswitch[i]=find;
        state[i]=need;
    }
    answer(dswitch.data(), state.data());
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24