#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;
vector<int> adj[maxn];
vector<pll> edge;
int con(vector<int> a){
set<int> cur;
for(auto x : a) cur.insert(x);
int cnt = 0;
for(auto [a, b] : edge) if(cur.count(a) && cur.count(b)) cnt++;
return cnt;
}
int qry(vector<int> a){
// cout<<"q : ";
// for(auto x : a) cout<<x<<" ";
// cout<<"\n";
// int op;
// cin>>op;
// cout<<"con : "<<con(a)<<"\n";
// return op < int(a.size()) - con(a);
vector<int> cur(n);
for(auto x : a) cur[x - 1] = 1;
int op = Query(cur);
return op < int(a.size()) - con(a);
}
void add(int a, int b){
adj[a].pb(b);
adj[b].pb(a);
edge.eb(a, b);
}
void Solve(int _n){
n = _n;
vector<int> q;
for(int rd = 0; rd < n - 1; rd++){
vector<int> cand;
for(int j = 1; j <= n; j++) cand.pb(j);
int l = 0, r = cand.size() - 1;
while(l + 1 < r){
// cout<<"bs : "<<l<<" "<<r<<"\n";
int m = (l + r) / 2;
vector<int> a, b;
for(int i = l; i <= m; i++) a.pb(cand[i]);
for(int i = m + 1; i <= r; i++) b.pb(cand[i]);
if(qry(a)) r = m;
else if(qry(b)) l = m + 1;
else break;
}
if(r == l + 1){
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 = mid;
else L = mid + 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 = mid;
else L = mid + 1;
}
add(fr, cand[L]);
}
int pos = 1;
for(int i = 1; i <= n; i++){
if(adj[i].size() == 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;
}
// cout<<"ans : ";
// for(auto x : ans) cout<<x<<" ";
// cout<<"\n";
Answer(ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
976 KB |
# of queries: 2847 |
| 2 |
Correct |
31 ms |
720 KB |
# of queries: 2838 |
| 3 |
Correct |
31 ms |
984 KB |
# of queries: 2972 |
| 4 |
Correct |
36 ms |
468 KB |
# of queries: 2965 |
| 5 |
Correct |
32 ms |
976 KB |
# of queries: 2980 |
| 6 |
Correct |
38 ms |
976 KB |
# of queries: 2989 |
| 7 |
Correct |
36 ms |
976 KB |
# of queries: 2961 |
| 8 |
Correct |
36 ms |
856 KB |
# of queries: 2831 |
| 9 |
Correct |
37 ms |
720 KB |
# of queries: 2973 |
| 10 |
Correct |
19 ms |
476 KB |
# of queries: 1729 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 12 |
| 15 |
Correct |
2 ms |
600 KB |
# of queries: 101 |
| 16 |
Correct |
2 ms |
460 KB |
# of queries: 237 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
976 KB |
# of queries: 2847 |
| 2 |
Correct |
31 ms |
720 KB |
# of queries: 2838 |
| 3 |
Correct |
31 ms |
984 KB |
# of queries: 2972 |
| 4 |
Correct |
36 ms |
468 KB |
# of queries: 2965 |
| 5 |
Correct |
32 ms |
976 KB |
# of queries: 2980 |
| 6 |
Correct |
38 ms |
976 KB |
# of queries: 2989 |
| 7 |
Correct |
36 ms |
976 KB |
# of queries: 2961 |
| 8 |
Correct |
36 ms |
856 KB |
# of queries: 2831 |
| 9 |
Correct |
37 ms |
720 KB |
# of queries: 2973 |
| 10 |
Correct |
19 ms |
476 KB |
# of queries: 1729 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 12 |
| 15 |
Correct |
2 ms |
600 KB |
# of queries: 101 |
| 16 |
Correct |
2 ms |
460 KB |
# of queries: 237 |
| 17 |
Correct |
715 ms |
1028 KB |
# of queries: 19415 |
| 18 |
Correct |
720 ms |
1240 KB |
# of queries: 19202 |
| 19 |
Correct |
722 ms |
804 KB |
# of queries: 19415 |
| 20 |
Correct |
656 ms |
1492 KB |
# of queries: 18195 |
| 21 |
Correct |
592 ms |
1036 KB |
# of queries: 17121 |
| 22 |
Correct |
739 ms |
1260 KB |
# of queries: 19444 |
| 23 |
Correct |
731 ms |
1008 KB |
# of queries: 19406 |
| 24 |
Correct |
208 ms |
728 KB |
# of queries: 8961 |
| 25 |
Correct |
722 ms |
1032 KB |
# of queries: 18991 |
| 26 |
Correct |
646 ms |
1048 KB |
# of queries: 17782 |
| 27 |
Correct |
218 ms |
732 KB |
# of queries: 8945 |
| 28 |
Correct |
381 ms |
1048 KB |
# of queries: 14912 |
| 29 |
Correct |
373 ms |
792 KB |
# of queries: 14894 |
| 30 |
Correct |
368 ms |
796 KB |
# of queries: 14912 |
