제출 #542430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542430		two_sides	Minerals (JOI19_minerals)	C++17	100 / 100	61 ms	3540 KiB

minerals

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

using namespace std;

bool query(int x) {
  static int last = 0;
  int cur = Query(x);
  bool ans = cur != last;
  last = cur;
  return ans;
}

void solve(vector<int> l, vector<int> r, bool fill) {
  int n = (int) l.size(), m = ceil(n * 0.36);
  if (fill) {
    m = n - m;
  }
  if (n == 1) {
    Answer(l[0], r[0]);
    return;
  }
  if (fill) {
    for (int i = n - 1; i >= m; --i) {
      query(l[i]);
    }
  } else {
    for (int i = 0; i < m; ++i) {
      query(l[i]);
    }
  }
  vector<int> left, right;
  random_shuffle(r.begin(), r.end());
  for (auto i : r) {
    if ((int) left.size() == m) {
      right.push_back(i);
    } else if ((int) right.size() == n - m) {
      left.push_back(i);
    } else if (query(i)) {
      right.push_back(i);
    } else {
      left.push_back(i);
    }
  }
  solve(vector<int>(l.begin(), l.begin() + m), left, true);
  solve(vector<int>(l.begin() + m, l.end()), right, false);
}

void Solve(int n) {
  vector<int> l, r;
  for (int i = 1; i <= n * 2; ++i) {
    if (query(i) == 1) {
      l.push_back(i);
    } else {
      r.push_back(i);
    }
  }
  solve(l, r, true);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10