Submission #1302101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302101		timeflew	Cave (IOI13_cave)	C++20	0 / 100	2 ms	416 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, 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;
        while(l<=r) {
            int mid=(l+r)/2;
            change(l, mid);
            int res=tryCombination(s);            
            change(l, mid);
            if(res!=sign)
                final_pos=l, r=mid-1;
            else
                l=mid+1;
        }
        vis[final_pos]=1;
        an[i]=final_pos;
        s[final_pos]=sign;
    }
    answer(s, an);
}

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