Submission #412124

#	Time	Username	Problem	Language	Result	Execution time	Memory
412124		MDario	Cave (IOI13_cave)	C++11	100 / 100	388 ms	452 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
int a[5000], r[5000], n;
int f(int lf, int rf, int k){
    if(lf==rf)return lf;
    int m=(lf+rf)/2, c;
    for(int i=lf; i<=m; i++){
        if(r[i]==-1)a[i]=(!a[i]);
    }
    c=tryCombination(a);
    for(int i=lf; i<=m; i++){
        if(r[i]==-1)a[i]=(!a[i]);
    }
    if(c>k||c==-1)return f(lf, m, k);
    else return f(m+1, rf, k);
}
void exploreCave(int N) {
    n=N;
    set<int> v;
    int c;
    for(int i=0; i<N; i++){
        a[i]=0;
        r[i]=-1;
    }
    for(int i=0; i<N; i++){
        c=tryCombination(a);
        if(c>i||c==-1){
            for(int t=0; t<N; t++){
                if(r[t]==-1)a[t]=(!a[t]);
            }
        }
        c=f(0, n-1, i);
        r[c]=i;
        a[c]=(!a[c]);
        v.erase(c);
    }
    answer(a, r);
    return ;
}

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