oj.uz

Submission #23209

# Submission time Handle Problem Language Result Execution time Memory
23209 2017-05-04T15:56:05 Z duongthoi1999 Park (JOI17_park) C++14
67 / 100
 759 ms 2264 KB 
#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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 2264 KB Output is correct
2 Correct 273 ms 2264 KB Output is correct
3 Correct 329 ms 2264 KB Output is correct
4 Correct 583 ms 2264 KB Output is correct
5 Correct 589 ms 2264 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 2264 KB Output is correct
2 Correct 619 ms 2264 KB Output is correct
3 Correct 659 ms 2264 KB Output is correct
4 Correct 549 ms 2264 KB Output is correct
5 Correct 729 ms 2264 KB Output is correct
6 Correct 619 ms 2264 KB Output is correct
7 Correct 593 ms 2264 KB Output is correct
8 Correct 633 ms 2264 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 2264 KB Output is correct
2 Correct 759 ms 2264 KB Output is correct
3 Correct 739 ms 2264 KB Output is correct
4 Correct 686 ms 2264 KB Output is correct
5 Correct 706 ms 2264 KB Output is correct
6 Correct 546 ms 2264 KB Output is correct
7 Correct 643 ms 2264 KB Output is correct
8 Correct 693 ms 2264 KB Output is correct
9 Correct 723 ms 2264 KB Output is correct
10 Correct 583 ms 2264 KB Output is correct
11 Correct 619 ms 2264 KB Output is correct
12 Correct 699 ms 2264 KB Output is correct
13 Correct 626 ms 2264 KB Output is correct
14 Correct 586 ms 2264 KB Output is correct
15 Correct 653 ms 2264 KB Output is correct
16 Correct 646 ms 2264 KB Output is correct
17 Correct 579 ms 2264 KB Output is correct
18 Correct 593 ms 2264 KB Output is correct
19 Correct 639 ms 2264 KB Output is correct
20 Correct 723 ms 2264 KB Output is correct

Subtask #5
0 / 23.0

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