Submission #23209

#	Time	Username	Problem	Language	Result	Execution time	Memory
23209		duongthoi1999	Park (JOI17_park)	C++14	67 / 100	759 ms	2264 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
typedef pair<ll, int> ii;
const int mod = (int) 1e9 + 7;
const ll inf = 1LL << 60;
const int maxn = (int) 1400;
const ld eps = 1e-9;

bool ask(int A, int B, int Place[]) {
    if(A > B) swap(A, B);
    //cout << "? " << A << ": " << Place[A] << ", " << B << ": " << Place[B] << endl;
    return Ask(A, B, Place);
}
void answer(int A, int B) {
    if(A > B) swap(A, B);
    //cout << A << ' ' << B << endl;
    Answer(A, B);
}
int n, Place[maxn], deg[maxn], pre[maxn];
vector<int> tree;
set<int> S;

void subtask1() {
    rep(i, 0, n) Place[i] = 0;
	rep(i, 0, n) {
        rep(j, i + 1, n) {
            Place[i] = Place[j] = 1;
            if(ask(i, j, Place)) Answer(i, j);
            Place[i] = Place[j] = 0;
        }
    }
}

bool inrange(int u, int l, int r, vector<int> &a) {
    rep(i, l, r + 1) Place[a[i]] = 0;
    bool f = !ask(0, u, Place);
    rep(i, l, r + 1) Place[a[i]] = 1;
    return f;
}

int find_pre(int u) {
    if(S.find(pre[u]) != S.end()) return pre[u];
    rep(i, 0, n) Place[i] = 1;
    vector<int> a;
    for (auto i : S) if(i != u) a.pb(i);
    int l = 0, r = SZ(a) - 1, res = u;
    while (l < r) {
        int md = (l + r) >> 1;
        if(inrange(u, l, md, a)) r = md;
        else l = md + 1;
    }
    if(inrange(u, l, r, a)) res = a[l];
    return pre[u] = res;
}

bool add_edge(int u, vector<int> &f) {
    int root = -1;
    per(i, 0, SZ(tree)) if(!f[i]) root = i, Place[tree[i]] = 1;
    if(root == -1) return 0;
    if(!ask(root, u, Place)) return 0;
    rep(i, 0, SZ(tree)) Place[tree[i]] = 0;
    int l = 0, r = SZ(tree) - 1;
    while (l < r) {
        int md = (l + r) >> 1;
        rep(i, 0, md + 1) if(!f[i]) Place[tree[i]] = 1;
        if(ask(root, u, Place)) r = md;
        else l = md + 1;
        rep(i, 0, md + 1) Place[tree[i]] = 0;
    }
    answer(tree[l], u);
    f[l] = 1;
    return 1;
}

void add_node(int u) {
    S.erase(S.find(u));
    rep(i, 0, n) Place[i] = (i == u);
    vector<int> f(SZ(tree), 0);
    //add_edge(u, f);
    while (add_edge(u, f)) {}
    tree.pb(u);
}

void process(int u) {
    while (1) {
        int v = find_pre(u);
        if(v == u) return add_node(u);
        process(v);
    }
}

void subtask4() {
    tree.pb(0);
    rep(i, 1, n) S.insert(i);
    while (!S.empty()) {
        int u = *S.begin();
        process(u);
    }
}

void subtask5() {

}

void Detect(int T, int N) {
	n = N;
	rep(i, 0, n) pre[i] = -1;
	if(T == 1) subtask4();
	if(T == 2) subtask4();
	if(T == 3) subtask4();
	if(T == 4) subtask4();
	if(T == 5) subtask4();
}

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