Submission #370264

#	Time	Username	Problem	Language	Result	Execution time	Memory
370264		Mamnoon_Siam	Park (JOI17_park)	C++17	77 / 100	2090 ms	956 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;

/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int N = 1500;
using bs = bitset<N>;

mt19937 rng(69);
int random(int l, int r) {
  return uniform_int_distribution<int>(l, r)(rng);
}

vi diff(vi a, vi b) {
  sort(all(a));
  sort(all(b));
  vi r;
  set_difference(all(a), all(b), back_inserter(r));
  return r;
}
static int Place[N];
bool ask(int u, int v, vi a) {
  if(u > v) swap(u, v);
  memset(Place, 0, sizeof Place);
  for(int i : a) Place[i] = 1;
  Place[u] = Place[v] = 1;
  return Ask(u, v, Place);
}

vector<ii> ans;

void solve(vi s) {
  sort(all(s));
  if(sz(s) <= 1) return;
  int x = random(0, sz(s)-1);
  int y = random(0, sz(s)-2);
  if(y >= x) ++y;
  x = s[x], y = s[y];
  vi path;
  for(int z : s) if(z != x and z != y) {
    if(!ask(x, y, diff(s, {z}))) {
      path.emplace_back(z);
    }
  }
  vi tmp = path;
  sort(all(tmp));
  sort(all(path), [&x,&path](int i, int j){
    return !ask(x, j, diff(path, {i}));
  });
  path.insert(path.begin(), x);
  path.emplace_back(y);
  vi notpath = diff(s, path);
  map<int, vi> mp;
  for(int u : notpath) {
    int lo = 1, hi = sz(path), opt = -1;
    while(lo <= hi) {
      int mid = (lo + hi) >> 1;
      if(ask(x, u, diff(s, vi(path.begin()+mid, path.end())))) {
        opt = mid;
        hi = mid-1;
      } else {
        lo = mid+1;
      }
    }
    mp[path[opt-1]].emplace_back(u);
  }
  for(int u : path) mp[u].emplace_back(u);
  for(int i = 1; i < sz(path); ++i) {
    ans.emplace_back(path[i-1], path[i]);
  }
  for(auto pa : mp) {
    solve(pa.se);
  }
}

void dumb(int n) {
  for(int i = 0; i < n; ++i) {
    for(int j = i+1; j < n; ++j) {
      if(ask(i, j, {i,j})) {
        Answer(i, j);
      }
    }
  }
}

void Detect(int T, int n) {
  if(T == 1) {
    dumb(n);
    return;
  }
  vi s(n); iota(all(s), 0);
  solve(s);
  for(ii x : ans) {
    if(x.fi > x.se) swap(x.fi, x.se);
    Answer(x.fi, x.se);
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23