제출 #1294279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294279		gregorjanjpg	Cave (IOI13_cave)	C++20	100 / 100	158 ms	532 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>; 

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

int INF = 1e9 + 1000; 

vec<int> door, dir_to_open_switch; 
int n; 

int help = 0; 

void find_switch_to_door(int x){
  // auto a = new int[n]; 
  vec<int> a(n); 
   
  F(0, n){
    a[i] = dir_to_open_switch[i] == -1 ? 0 : dir_to_open_switch[i]; 
  }
  int depth = tryCombination(a.data()); 
  help++; 

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

  // 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; 
  // cout << "door " << x << " is connected to switch: " << L << '\n'; 
  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; 

  door.assign(n, -1); 
  dir_to_open_switch.assign(n, -1); 

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

  vec<int> S(n); 
  vec<int> D(n); 

  for (int i = 0; i < n; i++){
    D[door[i]] = i; 
    S[door[i]] = dir_to_open_switch[door[i]]; 
  }
  
  // cout << help << " ok\n???\n"; 
  // if(help > 70'000) exit(1); 
  answer(S.data(), D.data()); 
}

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