Submission #16640

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
16640	2015-09-02 05:09:10	suhgyuho_william	Cave (IOI13_cave)	C++98	100 / 100	507 ms	604 KiB

cave

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "cave.h"
int ans[5002],door[5002],res[5002],resd[5002];
int test[5002],check[5002];
void exploreCave(int N) {
    //ans[0]=ans[1]=ans[2]=1; ans[3]=0;
    //door[0]=3; door[1]=1; door[2]=0; door[3]=2;
    int i,j,n=N;
    int left,mid,right;
    int num;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++) if(!check[j]) test[j]=0;
        num=tryCombination(test);
        if(num==i) ans[i]=1;
        else ans[i]=0;
        left=0; right=n-1;
        while(left<=right){
            mid=(left+right)/2;
            if(left==right) break;
            for(j=left;j<=mid;j++) if(!check[j]) test[j]=ans[i];
            for(j=mid+1;j<=right;j++) if(!check[j]) test[j]=1-ans[i];
            num=tryCombination(test);
            if(num==i) left=mid+1;
            else right=mid;
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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