oj.uz

Submission #370257

# Submission time Handle Problem Language Result Execution time Memory
370257 2021-02-23T15:45:29 Z Mamnoon_Siam Park (JOI17_park) C++17
67 / 100
 2000 ms 964 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;
  /*set<int> st(all(a));
  for(int x : b) {
    st.erase(x);
  } return vi(all(st));*/
}
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);
}

// bs onlyi[N];
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);
  }
}

// static int Place[1400];
void Detect(int T, int n) {
  // for(int i = 0; i < n; ++i) onlyi[i][i] = 1;
  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);
  }
  /*int i;
  for(i = 0 ; i < 2 ; i++) Place[i] = 0;
  for(i = 2 ; i < N ; i++) Place[i] = 1;
  if(Ask(3, 5, Place) != 1) return;
  Answer(2, 4);
  Answer(2, 5);
  Answer(3, 4);
  Place[0] = 1;
  Place[3] = 0;
  Place[5] = 0;
  if(Ask(0, 4, Place) != 0) return;
  Answer(0, 1);
  Answer(0, 3);
  Answer(1, 4);
  Answer(1, 2);*/
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 620 KB Output is correct
2 Correct 576 ms 876 KB Output is correct
3 Correct 668 ms 748 KB Output is correct
4 Correct 699 ms 748 KB Output is correct
5 Correct 851 ms 876 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 520 KB Output is correct
2 Correct 403 ms 492 KB Output is correct
3 Correct 889 ms 620 KB Output is correct
4 Correct 528 ms 492 KB Output is correct
5 Correct 509 ms 652 KB Output is correct
6 Correct 519 ms 620 KB Output is correct
7 Correct 421 ms 492 KB Output is correct
8 Correct 344 ms 620 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 492 KB Output is correct
2 Correct 426 ms 748 KB Output is correct
3 Correct 438 ms 492 KB Output is correct
4 Correct 664 ms 620 KB Output is correct
5 Correct 644 ms 748 KB Output is correct
6 Correct 696 ms 620 KB Output is correct
7 Correct 604 ms 716 KB Output is correct
8 Correct 559 ms 652 KB Output is correct
9 Correct 484 ms 668 KB Output is correct
10 Correct 484 ms 620 KB Output is correct
11 Correct 704 ms 684 KB Output is correct
12 Correct 537 ms 748 KB Output is correct
13 Correct 518 ms 760 KB Output is correct
14 Correct 528 ms 748 KB Output is correct
15 Correct 642 ms 684 KB Output is correct
16 Correct 417 ms 492 KB Output is correct
17 Correct 849 ms 780 KB Output is correct
18 Correct 708 ms 692 KB Output is correct
19 Correct 672 ms 720 KB Output is correct
20 Correct 555 ms 492 KB Output is correct

Subtask #5
0 / 23.0

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