/*
#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;
}
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(Query(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(Query(a)<Query(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(Query(a)<Query(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 '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 |
45 ms |
280 KB |
# of queries: 3066 |
| 2 |
Correct |
30 ms |
300 KB |
# of queries: 3102 |
| 3 |
Correct |
39 ms |
284 KB |
# of queries: 3266 |
| 4 |
Correct |
45 ms |
288 KB |
# of queries: 3261 |
| 5 |
Correct |
42 ms |
276 KB |
# of queries: 3277 |
| 6 |
Correct |
44 ms |
212 KB |
# of queries: 3189 |
| 7 |
Correct |
38 ms |
284 KB |
# of queries: 3275 |
| 8 |
Correct |
42 ms |
296 KB |
# of queries: 3105 |
| 9 |
Correct |
36 ms |
296 KB |
# of queries: 3188 |
| 10 |
Correct |
28 ms |
324 KB |
# of queries: 1832 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
200 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 17 |
| 15 |
Correct |
1 ms |
292 KB |
# of queries: 126 |
| 16 |
Correct |
4 ms |
200 KB |
# of queries: 281 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
280 KB |
# of queries: 3066 |
| 2 |
Correct |
30 ms |
300 KB |
# of queries: 3102 |
| 3 |
Correct |
39 ms |
284 KB |
# of queries: 3266 |
| 4 |
Correct |
45 ms |
288 KB |
# of queries: 3261 |
| 5 |
Correct |
42 ms |
276 KB |
# of queries: 3277 |
| 6 |
Correct |
44 ms |
212 KB |
# of queries: 3189 |
| 7 |
Correct |
38 ms |
284 KB |
# of queries: 3275 |
| 8 |
Correct |
42 ms |
296 KB |
# of queries: 3105 |
| 9 |
Correct |
36 ms |
296 KB |
# of queries: 3188 |
| 10 |
Correct |
28 ms |
324 KB |
# of queries: 1832 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
200 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 17 |
| 15 |
Correct |
1 ms |
292 KB |
# of queries: 126 |
| 16 |
Correct |
4 ms |
200 KB |
# of queries: 281 |
| 17 |
Runtime error |
312 ms |
448 KB |
Execution killed with signal 13 |
| 18 |
Halted |
0 ms |
0 KB |
- |
