Submission #51931

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
51931	2018-06-22 16:33:20	imeimi2000	Cave (IOI13_cave)	C++17	100 / 100	1249 ms	584 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 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);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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