oj.uz

Submission #522665

# Submission time Handle Problem Language Result Execution time Memory
522665 2022-02-05T11:13:35 Z qwerasdfzxcl Park (JOI17_park) C++14
67 / 100
 450 ms 748 KB 
#include "park.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

static int Place[1400];
int a[2020];

int ask(int x, int y){return Ask(min(x, y), max(x, y), Place);}

void answer(int x, int y){
    if (x>y) swap(x, y);
    Answer(x, y);
}

void _sort(int n){
    vector<int> ans = {0};

    for (int i=1;i<n;i++){
        fill(Place, Place+1400, 1);

        int l = 1, r = (int)ans.size()-1, idx = 0;
        while(l<=r){
            int m = (l+r)>>1;
            for (int j=m;j<(int)ans.size();j++) Place[ans[j]] = 0;

            if (ask(0, i)) r = m-1;
            else l = m+1, idx = m;

            for (int j=m;j<(int)ans.size();j++) Place[ans[j]] = 1;
        }
        ans.insert(ans.begin()+idx+1, i);
    }
    for (int i=0;i<n;i++) a[i] = ans[i];
}

vector<int> adj[1400], C, W;
int visited[1400];

void dfs(int s){
    visited[s] = 1;
    W.push_back(s);
    for (auto &v:adj[s]) if (!visited[v] && Place[v]){
        dfs(v);
    }
}

void solve(vector<int> V, int x){
    fill(Place, Place+1400, 0);
    fill(visited, visited+1400, 0);
    Place[x] = 1;
    for (auto &v:V) Place[v] = 1;

    if (!ask(x, V[0])) return;

    W.clear();
    dfs(V[0]);
    int l = 0, r = (int)V.size()-1, idx = (int)V.size()-1;
    while(l<=r){
        int m = (l+r)>>1;
        for (int i=0;i<=m;i++) Place[W[i]] = 1;
        for (int i=m+1;i<(int)V.size();i++) Place[W[i]] = 0;

        if (ask(W[0], x)) idx = m, r = m-1;
        else l = m+1;
    }
    answer(W[idx], x);
    adj[W[idx]].push_back(x);
    adj[x].push_back(W[idx]);

    fill(Place, Place+1400, 0);
    for (auto &v:V) Place[v] = 1;

    vector<int> N;
    int mid = W[idx];
    for (auto &v:adj[W[idx]]) if (Place[v]) N.push_back(v);

    for (auto &nxt:N){
        W.clear();
        fill(Place, Place+1400, 0);
        fill(visited, visited+1400, 0);
        for (auto &v:V) Place[v] = 1;
        Place[mid] = 0;

        dfs(nxt);
        solve(W, x);
    }
}

void Detect(int T, int N) {
    for (int i=1;i<N;i++) a[i] = i;
    _sort(N);

    //printf("A = ");
    //for (int i=0;i<N;i++) printf("%d ", a[i]);
    //printf("\n");

    C.push_back(0);
    for (int i=1;i<N;i++){
        solve(C, a[i]);
        C.push_back(a[i]);
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 748 KB Output is correct
2 Correct 221 ms 604 KB Output is correct
3 Correct 209 ms 628 KB Output is correct
4 Correct 450 ms 620 KB Output is correct
5 Correct 409 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 548 KB Output is correct
2 Correct 326 ms 564 KB Output is correct
3 Correct 321 ms 656 KB Output is correct
4 Correct 324 ms 560 KB Output is correct
5 Correct 336 ms 560 KB Output is correct
6 Correct 299 ms 564 KB Output is correct
7 Correct 294 ms 556 KB Output is correct
8 Correct 339 ms 548 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 480 KB Output is correct
2 Correct 311 ms 576 KB Output is correct
3 Correct 335 ms 580 KB Output is correct
4 Correct 310 ms 568 KB Output is correct
5 Correct 307 ms 592 KB Output is correct
6 Correct 374 ms 620 KB Output is correct
7 Correct 361 ms 532 KB Output is correct
8 Correct 303 ms 572 KB Output is correct
9 Correct 311 ms 576 KB Output is correct
10 Correct 402 ms 608 KB Output is correct
11 Correct 321 ms 580 KB Output is correct
12 Correct 338 ms 676 KB Output is correct
13 Correct 350 ms 716 KB Output is correct
14 Correct 342 ms 588 KB Output is correct
15 Correct 329 ms 592 KB Output is correct
16 Correct 316 ms 544 KB Output is correct
17 Correct 431 ms 656 KB Output is correct
18 Correct 335 ms 592 KB Output is correct
19 Correct 352 ms 568 KB Output is correct
20 Correct 327 ms 572 KB Output is correct

Subtask #5
0 / 23.0

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