Submission #1004042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004042		Luvidi	Cave (IOI13_cave)	C++17	100 / 100	406 ms	600 KiB

cave

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

int f(int x){
    if(x==-1)return 1e9;
    return x;
}

void exploreCave(int n) {
    int ans1[n],ans2[n];
    memset(ans2,-1,sizeof(ans2));
    for(int i=0;i<n;i++){
        int a[n],x,y;
        for(int j=0;j<n;j++){
            if(ans2[j]==-1)a[j]=0;
            else a[j]=ans1[j];
        }
        x=tryCombination(a);
        y=x!=i;
        for(int j=0;j<n;j++){
            if(ans2[j]==-1)a[j]=y;
            else a[j]=ans1[j];
        }
        int l=0,r=n-1;
        while(l<r){
            int m=(l+r)/2;
            for(int j=0;j<n;j++){
                if(ans2[j]==-1)a[j]=y^(j<=m);
                else a[j]=ans1[j];
            }
            if(f(tryCombination(a))>i)r=m;
            else l=m+1;
        }
        ans1[l]=y^1;
        ans2[l]=i;
    }
    answer(ans1,ans2);
}

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