Submission #1307941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307941		ayaz	Cave (IOI13_cave)	C++20	0 / 100	182 ms	560 KiB

cave

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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define isz(x) int(x.size())

using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;

const int inf = 1e9;
const int sz = 2e5;

vi s, d;
int* convert(vector<int>& v) {
  return v.data();
}
int x;
int ask(vi s) {
  int S[isz(s)];
  for (int i = 0; i < isz(s); i++) S[i] = s[i];
  return tryCombination(S);
}
int solve(int l, int r, int c) {
  if (l == r) return l;
  int mid = (l + r) / 2;
  for (int i = l; i <= mid; i++) {
    if (d[i] != inf) continue;
    s[i] = c;
  }
  for (int i = mid + 1; i <= r; i++) {
    if (d[i] != inf) continue;
    s[i] = (c ^ 1);
  }
  // cout << "l and r : " << l << " " << r << endl;
  // for (int i = 0; i < isz(s); i++) cout << s[i] << " ";
  // cout << endl;
  int sm = ask(s);
  // cout << "aks(s) : " << sm << '\n';
  if (sm > x || sm == -1) {
    return solve(l, mid, c);
  }
  else 
    return solve(mid + 1, r, c);
}
void exploreCave(int N) {
  int n = N;
  d.resize(n, inf);
  s.assign(n, 0);

  while (ask(s) != -1) {
    int idx = ask(s);
    x = idx;
    vi S = s;
    auto val = solve(0, n - 1, 1);
    s = S;
    s[val] = 1;
    d[val] = idx;
  }

  s.assign(n, 1);
  while (ask(s) != -1) {
    int idx = ask(s);
    x = idx;
    vi S = s;
    auto val = solve(0, n - 1, 0);
    s = S;
    s[val] = 0;
    d[val] = idx;
  }
  answer(convert(s), convert(d));
}

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