Submission #297091

#	Time	Username	Problem	Language	Result	Execution time	Memory
297091		alexandra_udristoiu	Cave (IOI13_cave)	C++14	100 / 100	859 ms	760 KiB

cave

#include "cave.h"
#include<algorithm>
using namespace std;
static int p[5005], v[5005], s[5005];

void exploreCave(int n) {
    int i, st, dr, mid, j, c;
    for(i = 0; i < n; i++){
        p[i] = -1;
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[j] != -1){
                v[j] = s[j];
            }
            else{
                v[j] = 0;
            }
        }
        if( tryCombination(v) != i ){
            c = 0;
        }
        else{
            c = 1;
        }
        st = 0;
        dr = n - 1;
        while(st <= dr){
            mid = (st + dr) / 2;
            for(j = 0; j < n; j++){
                if(p[j] != -1){
                    v[j] = s[j];
                }
                else{
                    if(j <= mid){
                        v[j] = c;
                    }
                    else{
                        v[j] = 1 - c;
                    }
                }
            }
            if(tryCombination(v) != i){
                dr = mid - 1;
            }
            else{
                st = mid + 1;
            }
        }
        p[st] = i;
        s[st] = c;
    }
    answer(s, p);
}

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