Submission #1260947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260947		repmann	Cave (IOI13_cave)	C++20	100 / 100	498 ms	556 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int N;
int S[5000], T[5000], O[5000];
//int tryS[5000], tryO[5000], temp[5000];
//int tryCombination(int S[])
//{
//  cout << "Try:\n";
//  for(int i = 0; i < N; i++) cout << S[i];
//  cout << '\n';
//  for(int i = 0; i < N; i++) temp[i] = 0;
//  for(int i = 0; i < N; i++) if(S[i] == tryS[i]) temp[tryO[i]] = 1;
//  for(int i = 0; i < N; i++) if(!temp[i]) return i;
//  return -1;
//}
//void answer(int S[], int O[])
//{
//  cout << "Answer:\n";
//  for(int i = 0; i < N; i++) cout << S[i];
//  cout << '\n';
//  for(int i = 0; i < N; i++) cout << O[i] << " \n"[i == N];
//  return;
//}
void exploreCave(int n)
{
  N = n;
  vector <int> V(N);
  for(int i = 0; i < N; i++) V[i] = i;
  for(int i = 0; i < N; i++) O[i] = -1;
  auto Try = [&](int l, int r, bool state)
  {
    for(int i = 0; i < N; i++) T[i] = !state;
    for(int i = l; i <= r; i++) T[i] = state;
    for(int i = 0; i < N; i++)
    {
      if(O[i] < 0) continue;
      T[i] = S[i];
    }
    int ret = tryCombination(T);
    if(ret < 0) return N;
    return ret;
  };
  for(int i = 0; i < N; i++)
  {
//    cout << i << ":\n";
//    for(int x : V) cout << x << ' ';
//    cout << '\n';
    int ret, l = 0, r = V.size() - 1, s;
    bool state = Try(0, N - 1, 1) > i;
    while(l <= r)
    {
      s = (l + r) >> 1;
      if(Try(V[0], V[s], state) <= i) l = s + 1;
      else
      {
        r = s - 1;
        ret = V[s];
      }
    }
    S[ret] = state;
    O[ret] = i;
    for(int j = 0; j < V.size(); j++) if(V[j] == ret) V.erase(V.begin() + j);
  }
  return answer(S, O);
}
//int main()
//{
//  int n;
//  cin >> n;
//  for(int i = 0; i < n; i++) cin >> tryS[i];
//  for(int i = 0; i < n; i++) cin >> tryO[i];
//  exploreCave(n);
//  return 0;
//}

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