oj.uz

Submission #370262

# Submission time Handle Problem Language Result Execution time Memory
370262 2021-02-23T15:48:05 Z Mamnoon_Siam Park (JOI17_park) C++17
67 / 100
 2000 ms 828 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; ++i) {
      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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 800 KB Output is correct
2 Correct 599 ms 620 KB Output is correct
3 Correct 729 ms 748 KB Output is correct
4 Correct 796 ms 620 KB Output is correct
5 Correct 878 ms 688 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 620 KB Output is correct
2 Correct 421 ms 620 KB Output is correct
3 Correct 912 ms 776 KB Output is correct
4 Correct 551 ms 748 KB Output is correct
5 Correct 593 ms 492 KB Output is correct
6 Correct 539 ms 620 KB Output is correct
7 Correct 449 ms 620 KB Output is correct
8 Correct 363 ms 640 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 620 KB Output is correct
2 Correct 447 ms 492 KB Output is correct
3 Correct 435 ms 620 KB Output is correct
4 Correct 701 ms 748 KB Output is correct
5 Correct 670 ms 624 KB Output is correct
6 Correct 729 ms 732 KB Output is correct
7 Correct 631 ms 568 KB Output is correct
8 Correct 568 ms 492 KB Output is correct
9 Correct 507 ms 492 KB Output is correct
10 Correct 528 ms 620 KB Output is correct
11 Correct 683 ms 536 KB Output is correct
12 Correct 557 ms 748 KB Output is correct
13 Correct 512 ms 620 KB Output is correct
14 Correct 553 ms 620 KB Output is correct
15 Correct 687 ms 748 KB Output is correct
16 Correct 438 ms 524 KB Output is correct
17 Correct 877 ms 828 KB Output is correct
18 Correct 747 ms 548 KB Output is correct
19 Correct 750 ms 748 KB Output is correct
20 Correct 575 ms 648 KB Output is correct

Subtask #5
0 / 23.0

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