oj.uz

Submission #522668

# Submission time Handle Problem Language Result Execution time Memory
522668 2022-02-05T11:20:45 Z qwerasdfzxcl Park (JOI17_park) C++14
67 / 100
 425 ms 724 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;
    Place[W[idx]] = 0;

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

    vector<vector<int>> nxt_comp;
    for (auto &nxt:N){
        W.clear();
        dfs(nxt);
        if (!W.empty()) nxt_comp.push_back(W);
    }

    for (auto &nV:nxt_comp){
        solve(nV, 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[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 600 KB Output is correct
2 Correct 188 ms 584 KB Output is correct
3 Correct 198 ms 608 KB Output is correct
4 Correct 390 ms 608 KB Output is correct
5 Correct 425 ms 576 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 508 KB Output is correct
2 Correct 311 ms 488 KB Output is correct
3 Correct 275 ms 636 KB Output is correct
4 Correct 298 ms 424 KB Output is correct
5 Correct 277 ms 452 KB Output is correct
6 Correct 278 ms 424 KB Output is correct
7 Correct 273 ms 504 KB Output is correct
8 Correct 278 ms 512 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 468 KB Output is correct
2 Correct 264 ms 512 KB Output is correct
3 Correct 284 ms 416 KB Output is correct
4 Correct 286 ms 408 KB Output is correct
5 Correct 296 ms 440 KB Output is correct
6 Correct 336 ms 580 KB Output is correct
7 Correct 333 ms 528 KB Output is correct
8 Correct 278 ms 676 KB Output is correct
9 Correct 312 ms 452 KB Output is correct
10 Correct 319 ms 452 KB Output is correct
11 Correct 305 ms 584 KB Output is correct
12 Correct 292 ms 436 KB Output is correct
13 Correct 310 ms 432 KB Output is correct
14 Correct 305 ms 528 KB Output is correct
15 Correct 278 ms 516 KB Output is correct
16 Correct 288 ms 656 KB Output is correct
17 Correct 390 ms 564 KB Output is correct
18 Correct 302 ms 724 KB Output is correct
19 Correct 322 ms 440 KB Output is correct
20 Correct 301 ms 552 KB Output is correct

Subtask #5
0 / 23.0

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