oj.uz

답안 #522924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522924 2022-02-06T13:00:29 Z qwerasdfzxcl Park (JOI17_park) C++14
10 / 100
 274 ms 1112 KB 
#include "park.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
static int Place[1400];
int a[1400], Qcnt;
 
int ask(int x, int y){assert(++Qcnt<=20000); 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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 10 ms 464 KB Output is correct
3 Correct 9 ms 460 KB Output is correct
4 Correct 22 ms 496 KB Output is correct
5 Correct 40 ms 568 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 257 ms 1112 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 172 ms 964 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 524 KB Output is correct
2 Runtime error 196 ms 1052 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 274 ms 968 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -