oj.uz

Submission #522663

# Submission time Handle Problem Language Result Execution time Memory
522663 2022-02-05T11:10:00 Z qwerasdfzxcl Park (JOI17_park) C++14
10 / 100
 461 ms 860 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;
    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[W[idx]] = 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[3]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 860 KB Output is correct
2 Correct 220 ms 604 KB Output is correct
3 Correct 209 ms 640 KB Output is correct
4 Correct 461 ms 720 KB Output is correct
5 Correct 404 ms 632 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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