Submission #244762

#	Time	Username	Problem	Language	Result	Execution time	Memory
244762		DavidDamian	Cave (IOI13_cave)	C++11	100 / 100	259 ms	888 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
///Binary Search
///Greedy
///Find the position and correct states of the switches
#define debug(x) cout<<#x<<" = "<<x<<endl
int correct[5005];
int pos[5005];
int A[5005];
int locked[5005];
void Init(int n)
{
    for(int i=0;i<n;i++){
        A[i]=(locked[i]==-1)? 0 : locked[i];
    }
}
void findPosition(int id,int n)
{
    int L=0,R=n-1;
    while(L<R){
        int mid=(L+R)/2;
        if(correct[id]==0){
            for(int i=L;i<mid+1;i++){
                A[i]=(locked[i]==-1)? 0 : locked[i];
            }
            for(int i=mid+1;i<=R;i++){
                A[i]=(locked[i]==-1)? 1 : locked[i];
            }
        }
        else{
            for(int i=L;i<mid+1;i++){
                A[i]=(locked[i]==-1)? 1 : locked[i];
            }
            for(int i=mid+1;i<=R;i++){
                A[i]=(locked[i]==-1)? 0 : locked[i];
            }
        }
        if(tryCombination(A)!=id)
            R=mid;
        else
            L=mid+1;
    }
    pos[L]=id;
    locked[L]=correct[id];
}
void exploreCave(int n) {
    memset(locked,-1,sizeof locked);
    for(int i=0;i<n;i++){
        Init(n);
        if(tryCombination(A)!=i)
            correct[i]=0;
        else
            correct[i]=1;
        findPosition(i,n);
    }
    answer(locked,pos);
}

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