Submission #157299

#	Time	Username	Problem	Language	Result	Execution time	Memory
157299		my99n	Cave (IOI13_cave)	C++14	0 / 100	204 ms	640 KiB

cave

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

int a[5010], cc[5010], sw[5010];

void exploreCave(int n) {
    memset(cc, -1, sizeof cc);
    memset(sw, -1, sizeof sw);

    for(int i = 0; i < n; i++){
        if (cc[i]!=-1 && sw[i]!=-1) continue;
        for(int j = 0; j < n; j++){
            if (j < i)  a[j] = cc[j];
            else        a[j] = 0;
        }
        int result = tryCombination(a);
        if (result == -1) {
            for(int i = 0; i < n; i++) sw[i] = a[i];
        }
        bool io = (result > i);
        if (io) sw[i] = 0;
        else    sw[i] = 1;

        if (cc[i]!=-1 && sw[i]!=-1) continue;
       
        int l = i, r = n-1;
        while(l < r) {
            int mid = (l+r)>>1;
            for(int j = 0; j < i; j++) a[j] = cc[j]; 
            for(int j = i; j <= mid; j++) a[j] = 1;
            int res = tryCombination(a);
            if (res == -1) {
                for(int i = 0; i < n; i++) sw[i] = a[i];
            }
            if ((res>i)^io)     r = mid;
            else                l = mid + 1;
        }

        if (cc[i]!=-1 && sw[i]!=-1) continue;
        cc[i] = l;
    }
    answer(sw, cc);
}

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