Submission #1013074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013074		amirhoseinfar1385	동굴 (IOI13_cave)	C++17	21 / 100	256 ms	65536 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;

int pors(vector<int>ers){
//    cout<<"wtf: ";
    for(int i=0;i<n;i++){
    //    cout<<ers[i]<<" ";
        pa[i]=ers[i];
    }
  //  cout<<endl;
    int z=tryCombination(pa);
    if(z==-1){
        z=n+1;
    }
    return z;
}

void solve(vector<int>cand,int lev){
//    cout<<lev<<endl;
    if(lev==n){
        return ;
    }
    vector<int>ers(n);
    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;
    vector<int>fake;
    //cout<<lev<<" "<<low<<" "<<cand[low]<<" "<<tof<<endl;
    for(int i=0;i<(int)cand.size();i++){
        if(i!=low){
            fake.push_back(cand[i]);
        }
    }
    unnow.push_back(cand[low]);
    return solve(fake,lev+1);
}

void exploreCave(int N) {
    n=N;
    vector<int>v;
    for(int i=0;i<n;i++){
        v.push_back(i);
    }
    solve(v,0);
    answer(vas,vasl);    
}

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