oj.uz

Submission #370264

# Submission time Handle Problem Language Result Execution time Memory
370264 2021-02-23T15:48:52 Z Mamnoon_Siam Park (JOI17_park) C++17
77 / 100
 2000 ms 956 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 364 KB Output is correct
3 Correct 12 ms 364 KB Output is correct
4 Correct 12 ms 364 KB Output is correct
5 Correct 12 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 620 KB Output is correct
2 Correct 583 ms 620 KB Output is correct
3 Correct 667 ms 620 KB Output is correct
4 Correct 693 ms 748 KB Output is correct
5 Correct 848 ms 876 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 492 KB Output is correct
2 Correct 434 ms 492 KB Output is correct
3 Correct 963 ms 748 KB Output is correct
4 Correct 556 ms 492 KB Output is correct
5 Correct 554 ms 492 KB Output is correct
6 Correct 544 ms 748 KB Output is correct
7 Correct 447 ms 492 KB Output is correct
8 Correct 369 ms 524 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 620 KB Output is correct
2 Correct 462 ms 620 KB Output is correct
3 Correct 457 ms 620 KB Output is correct
4 Correct 698 ms 620 KB Output is correct
5 Correct 665 ms 748 KB Output is correct
6 Correct 724 ms 620 KB Output is correct
7 Correct 588 ms 876 KB Output is correct
8 Correct 580 ms 748 KB Output is correct
9 Correct 510 ms 760 KB Output is correct
10 Correct 492 ms 620 KB Output is correct
11 Correct 674 ms 620 KB Output is correct
12 Correct 559 ms 876 KB Output is correct
13 Correct 492 ms 620 KB Output is correct
14 Correct 554 ms 620 KB Output is correct
15 Correct 658 ms 764 KB Output is correct
16 Correct 426 ms 620 KB Output is correct
17 Correct 847 ms 748 KB Output is correct
18 Correct 737 ms 820 KB Output is correct
19 Correct 682 ms 764 KB Output is correct
20 Correct 586 ms 748 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 956 KB Time limit exceeded
2 Halted 0 ms 0 KB -