oj.uz

Submission #23208

# Submission time Handle Problem Language Result Execution time Memory
23208 2017-05-04T15:17:46 Z duongthoi1999 Park (JOI17_park) C++14
77 / 100
 699 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);
    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;
}

void add_node(int u) {
    S.erase(S.find(u));
    rep(i, 0, n) Place[i] = (i == u);
    int l = 0, r = SZ(tree) - 1;
    while (l < r) {
        int md = (l + r) >> 1;
        rep(i, 0, md + 1) Place[tree[i]] = 1;
        if(ask(0, u, Place)) r = md;
        else l = md + 1;
        rep(i, 0, md + 1) Place[tree[i]] = 0;
    }
    answer(tree[l], u);
    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) subtask1();
	if(T == 2) subtask4();
	if(T == 3) subtask4();
	if(T == 4) subtask4();
	if(T == 5) subtask5();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2132 KB Output is correct
2 Correct 6 ms 2132 KB Output is correct
3 Correct 6 ms 2132 KB Output is correct
4 Correct 6 ms 2132 KB Output is correct
5 Correct 6 ms 2132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 2264 KB Output is correct
2 Correct 253 ms 2264 KB Output is correct
3 Correct 299 ms 2264 KB Output is correct
4 Correct 539 ms 2264 KB Output is correct
5 Correct 546 ms 2264 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 2264 KB Output is correct
2 Correct 563 ms 2264 KB Output is correct
3 Correct 609 ms 2264 KB Output is correct
4 Correct 493 ms 2264 KB Output is correct
5 Correct 686 ms 2264 KB Output is correct
6 Correct 596 ms 2264 KB Output is correct
7 Correct 543 ms 2264 KB Output is correct
8 Correct 589 ms 2264 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 2264 KB Output is correct
2 Correct 699 ms 2264 KB Output is correct
3 Correct 696 ms 2264 KB Output is correct
4 Correct 623 ms 2264 KB Output is correct
5 Correct 653 ms 2264 KB Output is correct
6 Correct 509 ms 2264 KB Output is correct
7 Correct 593 ms 2264 KB Output is correct
8 Correct 643 ms 2264 KB Output is correct
9 Correct 679 ms 2264 KB Output is correct
10 Correct 553 ms 2264 KB Output is correct
11 Correct 566 ms 2264 KB Output is correct
12 Correct 646 ms 2264 KB Output is correct
13 Correct 599 ms 2264 KB Output is correct
14 Correct 549 ms 2264 KB Output is correct
15 Correct 623 ms 2264 KB Output is correct
16 Correct 586 ms 2264 KB Output is correct
17 Correct 536 ms 2264 KB Output is correct
18 Correct 546 ms 2264 KB Output is correct
19 Correct 583 ms 2264 KB Output is correct
20 Correct 679 ms 2264 KB Output is correct

Subtask #5
0 / 23.0

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