Submission #1302111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302111		timeflew	동굴 (IOI13_cave)	C++20	100 / 100	159 ms	520 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=5e3;

bool vis[mxN];
int s[mxN], an[mxN];

void change(int i, int j) {
    for(int pos=i; pos<=j; pos++) {
        if(vis[pos])
            continue;
        s[pos]=!s[pos];
    }
}

void exploreCave(int N) {
    for(int i=0; i<N; i++) {
        int l=0, r=N-1, final_pos=0;
        int sign=tryCombination(s)==i?0:1;
        // cout<<"round "<<i<<" sign"<<sign<<" tryCombination"<<tryCombination(s)<<endl;
        while(l<=r) {
            int mid=(l+r)/2;
            change(l, mid);
            int res=(tryCombination(s)==i?0:1);
            // cout<<"l mid res"<<l<<' '<<mid<<' '<<res<<endl;            
            change(l, mid);
            if(res!=sign)
                final_pos=mid, r=mid-1;
            else
                l=mid+1;
        }
        // cout<<i<<"final_pos"<<' '<<final_pos<<endl;
        vis[final_pos]=1;
        an[final_pos]=i;
        s[final_pos]=!sign;
    }
    answer(s, an);
}

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