| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 950910 | phoenix0423 | 도서관 (JOI18_library) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1005;
#include "library.h"
int n;
deque<int> dq;
set<int> st;
int deg[maxn];
vector<int> adj[maxn];
int ed[maxn];
int eg = 0;
int qry(vector<int> a){
int op = Query(a);
return op < a.size();
}
void add(int a, int b){
adj[a].pb(b);
adj[b].pb(a);
deg[a] ++, deg[b] ++;
if(deg[a] == 2) st.insert(a);
if(deg[b] == 2) st.insert(b);
if(deg[a] == 1 && deg[b] == 1) ed[a] = 1;
eg++;
}
void fix(){
for(int i = 1; i <= n; i++){
if(!ed[i] && deg[i] == 1) deg[i] = 2;
if(ed[i]) ed[i] = 0;
}
}
void Solve(int _n){
n = _n;
vector<int> q;
while(eg < n - 1){
vector<int> cand;
for(int j = 1; j <= n; j++) if(!st.count(j) && !ed[j]) cand.pb(j);
if(cand.size() < 2){
fix();
continue;
}
int l = 0, r = cand.size() - 1;
int ok = 0;
while(l < r){
int m = (l + r) / 2;
vector<int> a, b;
for(int i = 0; i <= m; i++) a.pb(cand[i]);
for(int i = m + 1; i <= r; i++) b.pb(cand[i]);
if(qry(a)) r = m, ok = 1;
else if(qry(b)) l = m + 1, ok = 1;
else break;
}
if(r == l + 1 && ok){
add(cand[l], cand[r]);
continue;
}
int m = (l + r) / 2;
int L = l, R = m;
while(L < R){
int mid = (L + R) / 2;
vector<int> a;
for(int i = m + 1; i < r; i++) a.pb(cand[i]);
for(int i = L; i <= mid; i++) a.pb(cand[i]);
if(qry(a)) R = m;
else L = m + 1;
}
int fr = cand[L];
L = m + 1, R = r;
while(L < R){
int mid = (L + R) / 2;
vector<int> a;
a.pb(fr);
for(int i = L; i <= mid; i++) a.pb(cand[i]);
if(qry(a)) R = m;
else L = m + 1;
}
if(!ok){
vector<int> a = {fr, cand[L]};
if(!qry(a)){
fix();
continue;
}
}
add(fr, cand[L]);
}
int pos;
for(int i = 1; i <= n; i++){
if(deg[i] == 1){
pos = i;
break;
}
}
vector<int> ans;
int prev = -1;
while(true){
ans.pb(pos);
int ok = 0;
for(auto x : adj[pos]){
if(x != prev){
prev = pos, pos = x, ok = 1;
break;
}
}
if(!ok) break;
}
Answer(ans);
}
// signed main(void){
// int n;
// cin>>n;
// Solve(n);
// }