Submission #94637

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
94637	2019-01-22 03:49:33	Retro3014	Cave (IOI13_cave)	C++17	100 / 100	960 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
#include "cave.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
#define MAX_N 5000
void exploreCave(int N) {
    vector<int> a(N), b(N);
    int q[MAX_N+1];
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++)  q[j] = 1;
      for(int j=0; j<i; j++)  q[b[j]] = a[j];
      int t = tryCombination(q);
      if(t==i)  a[i] = 1;
      else  a[i] = 0;
      int s = 0, e = N-1, m;
      while(s<e){
        m = (s+e)/2;
        for(int j=0; j<N; j++)  q[j] = 1 - a[i];
        for(int j = s; j<=m; j++) q[j] = a[i];
        for(int j=0; j<i; j++)  q[b[j]] = a[j];
        if(tryCombination(q)==i)  e = m;
        else  s = m+1;
      }
      b[i] = s;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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