Submission #1231933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231933		dssfsuper2	Cave (IOI13_cave)	C++20	100 / 100	602 ms	548 KiB

cave

#include "cave.h"
bool isao(int res, int ser){
    return (res==-1 || res>ser);
}
int n;
bool query(int left, int right, int door, int norm[], int imposed[]){
	int norm2[n];
	for(int i = 0;i<n;i++){
		norm2[i]=norm[i];
	}
    for(int i = left;i<=right;i++)norm2[i]=1;
	for(int i = 0;i<n;i++){
		if(imposed[i]==1)norm2[i]=0;
	}
    return isao(tryCombination(norm2), door);
}
void exploreCave(int N) {
    n=N;
    int norm[n];
	int imposed[n];
	
    for(int i = 0;i<N;i++){
        norm[i]=0;
		imposed[i]=0;
    }
    int correct[n], doors[n];
	for(int i = 0;i<n;i++){
		correct[i]=0;
		doors[i]=0;
	}
    for(int i = 0;i<N;i++){
        bool norp=query(0, -1, i, norm, imposed);
        int left = 0;int right=N-1;
        for(int it = 0;it<13;it++){
			int mid = (left+right)/2;
			if(left==right)break;
            bool x = query(left, mid, i, norm, imposed);
            bool res = x==norp;
            if(res){
                left=mid+1;
            }
            else{
                right=mid;
        	}
			
		}
        doors[left]=i;
        correct[left]=(norp? 0 : 1);
        norm[left]=correct[left];
		if(correct[left]==0)imposed[left]=1;
    }
    answer(correct, doors);
}

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