oj.uz

Submission #370248

# Submission time Handle Problem Language Result Execution time Memory
370248 2021-02-23T15:33:24 Z Mamnoon_Siam Park (JOI17_park) C++17
0 / 100
 2000 ms 876 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) {
  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);
}

vector<ii> ans;

void solve(vi 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);
    }
  }
  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 Detect(int T, int n) {
  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[2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1754 ms 752 KB Output is correct
2 Correct 1657 ms 876 KB Output is correct
3 Execution timed out 2033 ms 620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 632 KB Output is correct
2 Correct 1610 ms 748 KB Output is correct
3 Correct 1528 ms 748 KB Output is correct
4 Execution timed out 2056 ms 720 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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