Submission #135726

#	Time	Username	Problem	Language	Result	Execution time	Memory
135726		Talant	Cave (IOI13_cave)	C++17	100 / 100	757 ms	768 KiB

cave

#include "cave.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

#define sc second
#define fr first
#define mk make_pair
#define pb push_back

using namespace std;

const int NN = (1e6 + 5);
const int inf = (1e9 + 7);

int n;
int ans[NN],s[NN],u[NN];
int rs[NN];

void exploreCave(int N) {
      n = N;

      for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) u[j] = 1;
            for (int j = 0; j < i; j ++) u[ans[j]] = s[ans[j]];

            int last = tryCombination(u);
            int l = 0,r = n - 1,fl = 1;

            while (r - l > 1) {
                  int m = (r + l) >> 1;
                  for (int j = m + 1; j <= r; j ++) u[j] = fl ^ 1;
                  for (int j = 0; j < i; j ++) u[ans[j]] = s[ans[j]];

                  int cur = tryCombination(u);
//                  for (int j = 0; j < n; j ++)
//                        cout << u[j] << " ";
//                  cout << endl;
//                  cout << l << " " << r << " " << cur << endl;
                  if ((cur != i && last != i) || (cur == i && last == i)) r = m;
                  else l = m + 1,fl ^= 1;
                  last = cur;
            }
            if (l == r) {
                  ans[i] = l;
                  s[l] = (last == i ? (fl ^ 1) : fl);
            }
            else {
                  u[r] = fl ^ 1;
                  for (int j = 0; j < i; j ++) u[ans[j]] = s[ans[j]];
                  int cur = tryCombination(u);
                  if ((cur == i && last == i) || (cur != i && last != i)) {
                        ans[i] = l;
                        s[l] = (cur == i ? (fl ^ 1) : (fl));
                  }
                  else {
                        ans[i] = r;
                        s[r] = (cur == i ? fl : (fl ^ 1));
                  }
            }
      }
      for (int i = 0; i < n; i ++)
            rs[ans[i]] = i;
      answer(s,rs);
}

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