Submission #1259580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259580		comgaTramAnh	Cave (IOI13_cave)	C++20	100 / 100	178 ms	568 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std; 
/*int tryCombination(vector <int> S) {
  for (int i = 0; i < (int) S.size(); i++) {
    cout << S[i] << ' '; 
  }
  cout << endl;
  fflush(stdout); 
  int ret;
  cin >> ret; 
  return ret; 
} 
void answer(vector <int> S, vector <int> D) {
  cout << "Answer is" << endl; 
  for (int i = 0; i < (int) S.size(); i++) {
    cout << S[i] << ' '; 
  }
  cout << endl;
  for (int i = 0; i < (int) D.size(); i++) {
    cout << D[i] << ' '; 
  }
  cout << endl; 
} */
void exploreCave(int N) {
  //vector <int> S(N), D(N);
  vector <int> finalSwitch(N), finalS(N);
  int S[N], D[N];
  vector <bool> found(N);
  for (int i = 0; i < N; i++) {
    S[i] = 0; 
    D[i] = i; 
    found[i] = false; 
  }             
  for (int i = 0; i < N; i++) {
    int tmp[N];
    for (int j = 0; j < N; j++) {
      tmp[j] = S[j]; 
    } 
    int door = tryCombination(tmp);
    finalS[i] = 1; 
    if (door != i) {
      finalS[i] = 0; 
      for (int j = 0; j < N; j++) {
        if (found[j] == false) {
          tmp[j] = 1 - tmp[j];  
        }
      }
    }
    int lo = 0, hi = N - 1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2; 
      for (int j = lo; j <= mid; j++) {
        if (found[j] == false) {
          tmp[j] = 1 - tmp[j];   
        }
      }
      door = tryCombination(tmp); 
      if (door != i) {
        finalSwitch[i] = mid; 
        hi = mid - 1; 
        for (int j = lo; j <= mid; j++) {
          if (found[j] == false) {
            tmp[j] = 1 - tmp[j]; 
          }
        }
      }
      else {
        lo = mid + 1;   
      }
    }
    found[finalSwitch[i]] = true;
    S[finalSwitch[i]] = finalS[i];
    D[finalSwitch[i]] = i;       
  }
  answer(S, D); 
}

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