Submission #1199786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199786		JungPS	동굴 (IOI13_cave)	C++20	100 / 100	567 ms	532 KiB

cave

#include "cave.h"
#include<iostream>
using namespace std;

int open[5007];
int sol[5007];
int n;
void solve(int x){
    //cout << "SOLVE " << x << endl;
    int l=0,r=n-1;
    int base[n];
    int fn;
    int ans=0;
    for(int i=0;i<n;++i) base[i]=open[i];
    for(int i=0;i<n;++i){
        if(base[i]==-1) base[i]=1;
    }
    int tmp=tryCombination(base);
    if(tmp>x || tmp==-1) fn=1;
    else fn=0;
    //cout << "fn = " << tryCombination(base) << " " << fn << endl;
    while(l<=r){
        for(int i=0;i<n;++i) base[i]=open[i];
        int mid=(l+r)>>1;
        for(int i=0;i<=mid;++i){
            if(base[i]==-1) base[i]=fn;
        }
        for(int i=mid;i<n;++i){
            if(base[i]==-1) base[i]=1-fn;
        }
        //for(int i=0;i<n;++i) cout << base[i] << " ";
        //cout << " A " << mid << " " << tryCombination(base) << endl;
        int tmp=tryCombination(base);
        if(tmp>x || tmp==-1){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    open[ans]=fn;
    sol[ans]=x;
    //cout << ans << endl;
}
void exploreCave(int N) {
    n=N;
    for(int i=0;i<N;++i) open[i]=-1;
    for(int i=0;i<N;++i){
        solve(i);
    }
    int a[n],b[n];
    for(int i=0;i<n;++i) a[i]=open[i];
    for(int i=0;i<n;++i) b[i]=sol[i];
    answer(open,sol);
}

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