Submission #1013077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013077		amirhoseinfar1385	Cave (IOI13_cave)	C++17	100 / 100	389 ms	916 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
int n,tof,vas[maxn],pa[maxn],vasl[maxn];
vector<int>unnow,ers;

int pors(vector<int>ers){
    for(int i=0;i<n;i++){
        pa[i]=ers[i];
    }
    int z=tryCombination(pa);
    if(z==-1){
        z=n+1;
    }
    return z;
}
vector<int>cand,fake;
void solve(int lev){
    if(lev==n){
        return ;
    }
    for(auto x:unnow){
        ers[x]=vas[x];
    }
    for(auto x:cand){
        ers[x]=0;
    }
    int z=pors(ers);
    if(z==lev){
        tof=1;
    }else if(z>lev){
        tof=0;
    }else{
        assert(0);
    }
    int low=0,high=(int)cand.size(),mid;
    while(high-low>1){
        mid=(high+low-1)>>1;
        for(auto x:unnow){
            ers[x]=vas[x];
        }
        for(int i=low;i<=mid;i++){
            ers[cand[i]]=tof;
        }
        for(int i=mid+1;i<(int)cand.size();i++){
            ers[cand[i]]=(1^tof);
        }
        for(int i=0;i<low;i++){
            ers[cand[i]]=(1^tof);
        }
        z=pors(ers);
        if(z==lev){
            low=mid+1;
        }else if(z>lev){
            high=mid+1;
        }else{
            assert(0);
        }
    }
    vas[cand[low]]=tof;
    vasl[cand[low]]=lev;
    fake.clear();
    for(int i=0;i<(int)cand.size();i++){
        if(i!=low){
            fake.push_back(cand[i]);
        }
    }
    unnow.push_back(cand[low]);
    swap(cand,fake);
    return solve(lev+1);
}

void exploreCave(int N) {
    n=N;
    ers.resize(n);
    for(int i=0;i<n;i++){
        cand.push_back(i);
    }
    solve(0);
    answer(vas,vasl);    
}

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