# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
125387 | 2019-07-05T07:31:00 Z | 송준혁(#3062) | Arranging Tickets (JOI17_arranging_tickets) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "park.h" using namespace std; static int N; static int P[2020]; static vector<int> V[2020]; static int Q[2020]; void f(int u){ vector<int> C; for (int i=0; i<N; i++) Q[i] = 0; for (int &v : V[u]){ Q[u] = Q[v] = 1; if (u < v){ if (Ask(u, v, Q)){ C.push_back(v); P[v] = u; Q[u] = Q[v] = 0; v = -1; } } else{ if (Ask(v, u, Q)){ C.push_back(v); P[v] = u; Q[u] = Q[v] = 0; v = -1; } } Q[u] = Q[v] = 0; } for (int i=0; i<N; i++) Q[i] = 1; for (int v : V[u]){ if (v == -1) continue; int L = 0, R = C.size()-1, k; while (L<=R){ int mid = (L+R)/2; for (int i=0; i<=mid; i++) Q[C[i]] = 0; if (u < v){ if (Ask(u, v, Q)) L = mid+1; else k = mid, R = mid-1; } else{ if (Ask(v, u, Q)) L = mid+1; else k = mid, R = mid-1; } for (int i=0; i<=mid; i++) Q[C[i]] = 1; } V[C[k]].push_back(v); } for (int v : C) f(v); } void Detect(int T, int n) { N = n; for (int i=1; i<N; i++) V[0].push_back(i); f(0); for (int i=1; i<N; i++){ if (P[i] < i) Answer(P[i], i); else Answer(i, P[i]); } }