Submission #1294150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294150		gregorjanjpg	Cave (IOI13_cave)	C++20	0 / 100	81 ms	98404 KiB

cave

#include "cave.h"

#include<bits/stdc++.h>

using namespace std;

using ll = long long; 
using pii = pair<int, int>; 
template<typename T> using vec = vector<T>; 

constexpr int tree_length = 1<<20;

#define F(l, r) for(int i = (int)l; i < (int)r; i++)

int INF = 1e9 + 1000; 

// void answer(int S[], int D[]);
// int tryCombination(int S[]); 

vec<int> door, dir_to_open_switch; 
int n; 

void find_door(int x){
  auto a = new int[n]; 
   
  F(0, n){
    a[i] = dir_to_open_switch[i] == -1 ? 0 : dir_to_open_switch[i]; 
  }
  int depth = tryCombination(a); 

  auto change_interval = [&](int L, int R){
    F(L, R){
      if(dir_to_open_switch[i] == -1) a[i] = !a[i]; 
    }
    return tryCombination(a); 
  }; 

  // try to switch the first half
  int L = 0, R = n-1; 
  while(L != R){
    int M = (L+R)/2; 
    int new_depth = change_interval(L, M); 
    bool change = (new_depth == x && depth != x) || (new_depth != x && depth == x); 
    depth = new_depth; 

    if(change){
      // they are on interval L, M; 
      R = M; 
    } else{
      L = M+1; 
    }
  }
  
  door[x] = L; 
  dir_to_open_switch[L] = (depth == x ? !a[L] : a[L]); // if depth = x => switch L closes x door
}

void exploreCave(int N){
  n = N; 
  // determine the first switch: binsearch: change a half of switches, if the depth changed to 1 or from 1 => 1 is in the first half, else it's in the other. At the end switch off 1 and look for 2
  door.assign(n, -1); 
  dir_to_open_switch.assign(n, -1); 

  F(0, n){
    find_door(i); 
  }

  auto S = new int[n]; 
  auto D = new int[n]; 

  for (int i = 0; i < n; i++){
    D[door[i]] = i; 
    S[i] = dir_to_open_switch[door[i]]; 
  }
  
  answer(S, D); 
}

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