oj.uz

Submission #522671

# Submission time Handle Problem Language Result Execution time Memory
522671 2022-02-05T11:24:30 Z qwerasdfzxcl Park (JOI17_park) C++14
100 / 100
 421 ms 844 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){
    if (visited[s]) return;
    visited[s] = 1;
    W.push_back(s);
    for (auto &v:adj[s]) if (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);
    fill(visited, visited+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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 11 ms 500 KB Output is correct
3 Correct 8 ms 380 KB Output is correct
4 Correct 21 ms 552 KB Output is correct
5 Correct 39 ms 592 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 580 KB Output is correct
2 Correct 203 ms 704 KB Output is correct
3 Correct 209 ms 588 KB Output is correct
4 Correct 401 ms 708 KB Output is correct
5 Correct 409 ms 648 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 588 KB Output is correct
2 Correct 273 ms 580 KB Output is correct
3 Correct 312 ms 540 KB Output is correct
4 Correct 299 ms 672 KB Output is correct
5 Correct 285 ms 556 KB Output is correct
6 Correct 280 ms 540 KB Output is correct
7 Correct 286 ms 556 KB Output is correct
8 Correct 276 ms 540 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 532 KB Output is correct
2 Correct 292 ms 684 KB Output is correct
3 Correct 301 ms 548 KB Output is correct
4 Correct 317 ms 580 KB Output is correct
5 Correct 276 ms 580 KB Output is correct
6 Correct 337 ms 752 KB Output is correct
7 Correct 330 ms 708 KB Output is correct
8 Correct 291 ms 544 KB Output is correct
9 Correct 293 ms 708 KB Output is correct
10 Correct 330 ms 580 KB Output is correct
11 Correct 319 ms 604 KB Output is correct
12 Correct 298 ms 564 KB Output is correct
13 Correct 302 ms 596 KB Output is correct
14 Correct 319 ms 560 KB Output is correct
15 Correct 285 ms 552 KB Output is correct
16 Correct 296 ms 540 KB Output is correct
17 Correct 388 ms 640 KB Output is correct
18 Correct 312 ms 696 KB Output is correct
19 Correct 333 ms 696 KB Output is correct
20 Correct 282 ms 580 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 836 KB Output is correct
2 Correct 358 ms 568 KB Output is correct
3 Correct 314 ms 572 KB Output is correct
4 Correct 327 ms 628 KB Output is correct
5 Correct 366 ms 580 KB Output is correct
6 Correct 376 ms 628 KB Output is correct
7 Correct 360 ms 600 KB Output is correct
8 Correct 339 ms 604 KB Output is correct
9 Correct 343 ms 720 KB Output is correct
10 Correct 327 ms 592 KB Output is correct
11 Correct 290 ms 576 KB Output is correct
12 Correct 364 ms 592 KB Output is correct
13 Correct 284 ms 580 KB Output is correct
14 Correct 381 ms 728 KB Output is correct
15 Correct 339 ms 596 KB Output is correct
16 Correct 278 ms 844 KB Output is correct
17 Correct 399 ms 668 KB Output is correct
18 Correct 301 ms 584 KB Output is correct