Submission #1088473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088473		anastasiskolio	Cave (IOI13_cave)	C++14	0 / 100	142 ms	600 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define MAXN 5000
using namespace std;

int S[MAXN], D[MAXN], alreadyInCorrectState[MAXN];

void adjustSwitches(int lo, int mid, int hi, int x, int y) {
  for (int i = lo; i <= mid; i++)
    if (!alreadyInCorrectState[i])
      S[i] = x;
  for (int i = mid + 1; i <= hi; i++)
    if (!alreadyInCorrectState[i])
      S[i] = y;
} 

int findTheCorrectDoor(int currentSwitch, int lo, int hi) {
  if (lo == hi)
    return lo;
  int mid = (lo + hi) / 2;
  adjustSwitches(lo, mid, hi, S[currentSwitch], !S[currentSwitch]);
  int ans = tryCombination(S);
  if (ans == -1 || ans > mid) 
    return findTheCorrectDoor(currentSwitch, lo, mid);
  else 
    return findTheCorrectDoor(currentSwitch, mid + 1, hi);
}

void findTheCorrectState(int currentSwitch, int N) {
  adjustSwitches(0, (N - 1) / 2, N - 1, 1, 1);
  int ans = tryCombination(S);
  S[currentSwitch] = ans == -1 || ans > currentSwitch;
  alreadyInCorrectState[currentSwitch] = 1;
}


void exploreCave(int N) {
  for (int i = 0; i < N; i++) {
    findTheCorrectState(i, N);
    D[i] = findTheCorrectDoor(i, 0, N - 1);
  }
  answer(S, D);
}

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