| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1165838 | hainam2k9 | Library (JOI18_library) | C++20 | 0 ms | 0 KiB |
#include "library.h"
#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
void solve(int n){
vector<int> v(n,1),num(n,0), adj[n+5];
bool vis[n+5];
int Start=0,End=0;
for(int i = 0; i<n; ++i){
v[i]=0;
if(Query(v)==1){
if(!Start) Start=i+1;
else End=i+1;
}
v[i]=1;
}
iota(num.begin(),num.end(),1);
while(sz(num)>2){
int l=1, r=sz(num)-1, pos1=0, pos2=0;
while(l<=r){
int mid=(l+r)>>1;
fill(v.begin(),v.end(),0);
for(int i = 0; i<=mid; ++i)
v[num[i]-1]=1;
if(Query(v)<=mid) pos1=mid, r=mid-1;
else l=mid+1;
}
l=0, r=pos1-1;
while(l<=r){
int mid=(l+r)>>1;
fill(v.begin(),v.end(),0);
for(int i = pos1; i>=mid; --i)
v[num[i]-1]=1;
if(Query(v)<=pos1-mid) pos2=mid, l=mid+1;
else r=mid-1;
}
cout << pos1 << " " << pos2 << endl;
adj[num[pos1]].pb(num[pos2]);
adj[num[pos2]].pb(num[pos1]);
num.erase(num.begin()+pos1);
}
vector<int> head,tail;
head.pb(Start), vis[Start]=1;
bool ok=0;
while(!ok){
ok=1;
for(int& x : adj[head.back()])
if(!vis[x]) head.pb(x), vis[x]=1, ok=0;
}
if(!vis[End]){
tail.pb(End), vis[End]=1;
ok=0;
while(!ok){
ok=1;
for(int& x : adj[tail.back()])
if(!vis[x]) tail.pb(x), vis[x]=1, ok=0;
}
while(!tail.empty()) head.pb(tail.back()), tail.pob();
}
Answer(head);
}