Submission #107183

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
107183	2019-04-22 11:12:32	stefdasca	Cave (IOI13_cave)	C++14	100 / 100	1258 ms	640 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
/*
        IOI 13-Cave
    The 70.000 queries limit suggests us that we should find the switch for each node in O(log n) questions.
    At each step, we will firstly find out which is the state for switch corresponding to door i, and then
we will use binary search on the possible range of the answer
*/
#include "cave.h"
#include<bits/stdc++.h>
void exploreCave(int N)
{
    int S[N+2], D[N+2];
    memset(S, 0, sizeof(S));
    memset(D, 0, sizeof(D));
    int P[N+2], pus[N+2];
    memset(P, 0, sizeof(P));
    memset(pus, 0, sizeof(pus));
    for(int i = 0; i < N; ++i)
    {
        int st = 0;
        int dr = N-1;
        for(int j = 0; j < N; ++j)
            if(pus[j])
                P[j] = S[j];
            else
                P[j] = 1;
        int ans = tryCombination(P);
        bool ce = 0;
        if(ans > i || ans == -1)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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