제출 #51931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51931		imeimi2000	동굴 (IOI13_cave)	C++17	100 / 100	1249 ms	584 KiB

cave

#include "cave.h"

int n;
int q[5000];
int pos[5000];
int sta[5000];
int ansS[5000];
int ansD[5000];

int question(int it, int s, int e) {
    for (int i = 0; i < n; ++i) {
        q[i] = (s <= i && i <= e);
    }
    for (int i = 0; i < it; ++i) {
        q[pos[i]] = sta[i];
    }
    return tryCombination(q);
}

void exploreCave(int N) {
    n = N;
    for (int i = 0; i < n; ++i) {
        q[i] = -1;
    }
    for (int i = 0; i < n; ++i) {
        sta[i] = (question(i, 0, -1) == i);
        int s = 0, e = n - 1;
        while (s < e) {
            int m = (s + e) / 2;
            int r = question(i, s, m);
            if ((r == i) == sta[i]) s = m + 1;
            else e = m;
        }
        pos[i] = s;
    }
    for (int i = 0; i < n; ++i) {
        ansD[pos[i]] = i;
        ansS[pos[i]] = sta[i];
    }
    answer(ansS, ansD);
}

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