Submission #112530

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
112530	2019-05-20 12:32:09	tjd229	Cave (IOI13_cave)	C++14	100 / 100	682 ms	616 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"
#define reg register
int _N;
void fill(int *a, int val, int s, int e, int *chair) {
  for (reg int i = 0; i < s; ++i) a[chair[i]] = 1 - val;
  for (reg int i = s; i <= e; ++i) a[chair[i]] = val;
  for (reg int i = e + 1; i < _N; ++i) a[chair[i]] = 1 - val;
}
void exploreCave(int N) {
  _N = N;
  int chair[5000], S[5000], D[5000];
  
  int &rem = _N;
  for (reg int i = 0; i < N; ++i) chair[i] = i;
  for (int i = 0; i < N; ++i) {
    int val = 0;
    fill(S, val, 0, rem - 1, chair);
    if (tryCombination(S) == i) val = 1;
    int l = 0, r = rem - 1;
    int pos = -1;
    while (l <= r) {
      int m = (l + r) >> 1;
      fill(S, val, l, m, chair);
      if (tryCombination(S) == i) l = m + 1;
      else r = m - 1, pos = m;
    }
    S[chair[pos]] = val;
    D[chair[pos]] = i;
    --rem;
    chair[pos] ^= chair[rem] ^= chair[pos] ^= chair[rem];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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