제출 #522676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522676		qwerasdfzxcl	Park (JOI17_park)	C++14	100 / 100	443 ms	860 KiB

park

#include "park.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

int ask(int x, int y){return Ask(min(x, y), max(x, y), Place);}
void answer(int x, int y){Answer(min(x, y), max(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=0;j<m;j++) Place[ans[j]] = 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;
        }
        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);

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23