/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/
#include<bits/stdc++.h>
#include "library.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}
#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
int n=v.size();
for(int i=0; i<n; i++)
cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
vector<T>ans;
for(T t:a)
if(ans.empty() || t!=ans.back())
ans.push_back(t);
return ans;
}
vi build(vvi g){
int n=g.size()-1;
for(int i=1; i<=n; i++){
sort(all(g[i]));
g[i]=UNQ(g[i]);
}
int cur=-1;
for(int i=1; i<=n; i++)
if(g[i].size()==1)
cur=i;
vector<bool>vis(n+1);
vi ans;
while(1){
vis[cur]=1;
ans.pb(cur);
bool ok=0;
for(int nbr:g[cur])
if(!vis[nbr])
cur=nbr,ok=1;
if(!ok)break;
}
return ans;
}
map<vi,int>asked;
int ask(vi v){
if(asked[v])return asked[v];
int popc=0;
for(int i=0; i<v.size(); i++)
popc+=v[i];
if(popc==1)
return asked[v]=1;
return asked[v]=Query(v);
}
void Solve(int n){
if(n==1){
vi ans={1};
Answer(ans);
return;
}
vvi g(n+1);
vector<bool>found1(n+1);
int s=-1,t=-1;
for(int i=2; i<=n; i++){
vi v(n);
v[0]=v[i-1]=1;
if(ask(v)==1){
if(s==-1)
s=i,found1[s]=1;
else {
t = i,found1[t]=1;
break;
}
}
}
g[1].pb(s);
g[s].pb(1);
if(t!=-1)
g[1].pb(t),g[t].pb(1);
while(1){
int l=1,r=n,ans=-1;
while(l<=r){
int m=(l+r)/2;
if(l==r && r==s)break;
vi a(n);
a[s-1]=1;
for(int i=l; i<=m; i++)
a[i-1]=1;
vi b(a);
b[s-1]=0;
for(int nbr:g[s])
a[nbr-1]=1,b[nbr-1]=1;
if(ask(a)<ask(b)){
r=m-1;
ans=m;
}
else
l=m+1;
}
if(ans==-1)break;
found1[s]=found1[ans]=1;
g[s].pb(ans);
g[ans].pb(s);
s=ans;
}
s=t;
while(s!=-1){
int l=1,r=n,ans=-1;
while(l<=r){
int m=(l+r)/2;
if(l==r && r==s)break;
vi a(n);
a[s-1]=1;
for(int i=l; i<=m; i++)
a[i-1]=1;
vi b(a);
b[s-1]=0;
for(int nbr:g[s])
a[nbr-1]=1,b[nbr-1]=1;
if(ask(a)<ask(b)){
r=m-1;
ans=m;
}
else
l=m+1;
}
if(ans==-1)break;
found1[s]=found1[ans]=1;
g[s].pb(ans);
g[ans].pb(s);
s=ans;
}
vi ans=build(g);
Answer(ans);
}
/*
5
4
2
5
3
1
*/
Compilation message
library.cpp: In function 'int ask(vi)':
library.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i=0; i<v.size(); i++)
| ~^~~~~~~~~
library.cpp: In function 'void usaco(std::string)':
library.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | freopen(FIN, "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~
library.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen(FOUT, "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
2624 KB |
# of queries: 2790 |
| 2 |
Correct |
42 ms |
2592 KB |
# of queries: 2864 |
| 3 |
Correct |
52 ms |
2912 KB |
# of queries: 2989 |
| 4 |
Correct |
37 ms |
2852 KB |
# of queries: 3009 |
| 5 |
Correct |
42 ms |
2996 KB |
# of queries: 3034 |
| 6 |
Correct |
55 ms |
2824 KB |
# of queries: 2918 |
| 7 |
Correct |
49 ms |
2832 KB |
# of queries: 3023 |
| 8 |
Correct |
56 ms |
2584 KB |
# of queries: 2851 |
| 9 |
Correct |
46 ms |
2880 KB |
# of queries: 2926 |
| 10 |
Correct |
30 ms |
1352 KB |
# of queries: 1679 |
| 11 |
Correct |
1 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
200 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 8 |
| 15 |
Correct |
3 ms |
320 KB |
# of queries: 106 |
| 16 |
Correct |
7 ms |
328 KB |
# of queries: 247 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
2624 KB |
# of queries: 2790 |
| 2 |
Correct |
42 ms |
2592 KB |
# of queries: 2864 |
| 3 |
Correct |
52 ms |
2912 KB |
# of queries: 2989 |
| 4 |
Correct |
37 ms |
2852 KB |
# of queries: 3009 |
| 5 |
Correct |
42 ms |
2996 KB |
# of queries: 3034 |
| 6 |
Correct |
55 ms |
2824 KB |
# of queries: 2918 |
| 7 |
Correct |
49 ms |
2832 KB |
# of queries: 3023 |
| 8 |
Correct |
56 ms |
2584 KB |
# of queries: 2851 |
| 9 |
Correct |
46 ms |
2880 KB |
# of queries: 2926 |
| 10 |
Correct |
30 ms |
1352 KB |
# of queries: 1679 |
| 11 |
Correct |
1 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
200 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 8 |
| 15 |
Correct |
3 ms |
320 KB |
# of queries: 106 |
| 16 |
Correct |
7 ms |
328 KB |
# of queries: 247 |
| 17 |
Correct |
606 ms |
76668 KB |
# of queries: 19043 |
| 18 |
Correct |
679 ms |
76616 KB |
# of queries: 19239 |
| 19 |
Correct |
694 ms |
78140 KB |
# of queries: 19389 |
| 20 |
Correct |
559 ms |
68788 KB |
# of queries: 18128 |
| 21 |
Correct |
514 ms |
60792 KB |
# of queries: 16887 |
| 22 |
Correct |
672 ms |
76576 KB |
# of queries: 18994 |
| 23 |
Correct |
669 ms |
78464 KB |
# of queries: 19484 |
| 24 |
Correct |
231 ms |
18852 KB |
# of queries: 8831 |
| 25 |
Correct |
596 ms |
75220 KB |
# of queries: 19060 |
| 26 |
Correct |
579 ms |
65664 KB |
# of queries: 17566 |
| 27 |
Correct |
231 ms |
18884 KB |
# of queries: 8786 |
| 28 |
Correct |
663 ms |
62056 KB |
# of queries: 15123 |
| 29 |
Correct |
680 ms |
61952 KB |
# of queries: 15107 |
| 30 |
Correct |
701 ms |
62236 KB |
# of queries: 15123 |
