Submission #459611

#	Time	Username	Problem	Language	Result	Execution time	Memory
459611		osmanallazov	Cave (IOI13_cave)	C++14	100 / 100	413 ms	676 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define ort (b+s)/2
using namespace std;
const int maxn = 5020;
bool used[maxn];
int ans[maxn], loc[maxn];
int ar[maxn];
void Fill( int b, int e, int t ) {
    for(int i=b;i<=e;i++)
        if( !used[i] ) ar[i] = t;
}
bool look(int b,int e ) {
    for(int i=b;i<=e;i++)
        if(!used[i]) return 1;
    return 0;
}
int trycom(int ar[]){
    int t=tryCombination( ar );
    if(t==-1) t=1e9;
    return t;
}
int find( int n, int b, int s, int val ) {
    if(b==s) return b;
    if(!look(b,ort)) return find( n, ort+1, s, val );
    if(!look( ort+1,s)) return find( n, b, ort, val );
    Fill(b,ort,val);
    Fill(ort+1,s,!val);
    if(trycom(ar)>n) return find(n,b,ort,val );
    return find(n,ort+1,s,val);
}
void exploreCave(int N) {
    for(int i=0;i<N;i++) {
        Fill(0,N-1,0);
        int val=0;
        if(trycom(ar)>i)val=0;
        else val=1;
        int t=find(i,0,N-1,val);
        loc[t]=i;
        ar[t]=ans[i]=val;
        used[t]=1;
    }
    answer(ar,loc);
}

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