#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
const int N=4e5+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;
int n;
int col[N],ind[N],ans[N];
vector<int> g[N];
bool dfsc(int v,int par=-1){
col[v]=1;
trav(to,g[v]){
if (col[to]==2)continue;
if (to!=par && col[to]==1)return true;
if (dfsc(to,v))return true;
}
col[v]=2;
return false;
}
bool cikl(){
FORT(i,0,n)col[i]=0;
FORT(i,1,n){
if (!col[i] && dfsc(i))return true;
}
return false;
}
vector<int> vc;
void dfs(int v){
col[v]=1;
trav(to,g[v]){
if (!col[to])dfs(to);
}
vc.ad(v);
}
void topsort(int k){
vc.clear();
FORT(i,0,n){
col[i]=0;
ans[i]=0;
}
FORT(i,1,k){
int v=ind[i];
if (!col[v])dfs(v);
}
//int qdljbj;
FOR(i,vc.size()){
ans[vc[i]]=i+1;
}
}
vector<int> hg[N];
void dfsh(int v){
col[v]=1;
trav(to,hg[v]){
if (!col[to])dfsh(to);
}
vc.ad(v);
}
void vts(bool hak){
vc.clear();
FORT(i,0,n){
col[i]=0;
ans[i]=0;
}
if (!hak){
FOR(i,n){
if (!col[i])dfs(i);
}
}
else{
FOR(i,n){
if (!col[i])dfsh(i);
}
}
FOR(i,vc.size()){
ans[vc[i]]=i+1;
}
}
int tv[N];
int main(){
fastio;
cin>>n;
//cout<<n<<endl;
FOR(i,n){
cin>>tv[i];
ind[tv[i]]=i;
}
//assert(tv[0]==1 && tv[1]==2 && tv[2]==3);
//cout<<i<<endl;
//cout<<1<<endl;
int qanq=0;
FORT(i,2,n){
FORTD(j,i-1,1){
//cout<<1<<endl;
int a=ind[i];
int b=ind[j];
g[b].ad(a);
//cout<<1<<endl;
if (cikl()){
g[b].pop_back();
continue;
}
//cout<<1<<endl;
topsort(i);
cout<<"query ";
FOR(k,n){
if (ans[k])cout<<ans[k]<<" ";
else cout<<tv[k]<<" ";
}
cout<<endl;
fflush(stdout);
int pat;
cin>>pat;
//if (n==4 && qanq==5 && !pat)assert(0);
//if (qanq==5)assert(0);
qanq++;
//3assert(!pat);
g[b].pop_back();
if (!pat){
g[a].ad(b);
hg[b].ad(a);
//cout<<a<<" "<<b<<endl;
}
//else cout<<a<<" "<<b<<endl;
}
}
assert(qanq<=5000);
cout<<"end"<<endl;
fflush(stdout);
FORT(i,0,n){
sort(all(g[i]));
sort(all(hg[i]));
}
vts(false);
bool bl=false;
FOR(i,n){
if (ans[i]<tv[i])bl=true;
if (!bl && ans[i]>tv[i])assert(0);
cout<<ans[i]<<" ";
}
cout<<endl;
vts(true);
bl=false;
FOR(i,n){
if (n-ans[i]+1>tv[i])bl=true;
if (!bl && n-ans[i]+1<tv[i])assert(0);
cout<<n-ans[i]+1<<" ";
}
cout<<endl;
fflush(stdout);
return 0;
}
Compilation message
zagonetka.cpp: In function 'void topsort(int)':
zagonetka.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
zagonetka.cpp:72:5: note: in expansion of macro 'FOR'
FOR(i,vc.size()){
^~~
zagonetka.cpp: In function 'void vts(bool)':
zagonetka.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
zagonetka.cpp:103:5: note: in expansion of macro 'FOR'
FOR(i,vc.size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19192 KB |
Output is correct |
| 2 |
Correct |
19 ms |
19064 KB |
Output is correct |
| 3 |
Correct |
19 ms |
19064 KB |
Output is correct |
| 4 |
Correct |
19 ms |
19192 KB |
Output is correct |
| 5 |
Correct |
19 ms |
19192 KB |
Output is correct |
| 6 |
Correct |
19 ms |
19064 KB |
Output is correct |
| 7 |
Correct |
19 ms |
19064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
19064 KB |
Output is correct |
| 2 |
Correct |
44 ms |
19148 KB |
Output is correct |
| 3 |
Correct |
59 ms |
19192 KB |
Output is correct |
| 4 |
Correct |
58 ms |
19192 KB |
Output is correct |
| 5 |
Correct |
29 ms |
19112 KB |
Output is correct |
| 6 |
Correct |
44 ms |
19152 KB |
Output is correct |
| 7 |
Correct |
22 ms |
19068 KB |
Output is correct |
| 8 |
Correct |
27 ms |
19192 KB |
Output is correct |
| 9 |
Correct |
52 ms |
19192 KB |
Output is correct |
| 10 |
Correct |
28 ms |
19144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19192 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
19096 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
19144 KB |
Output is correct |
| 2 |
Correct |
110 ms |
19152 KB |
Output is correct |
| 3 |
Correct |
91 ms |
19148 KB |
Output is correct |
| 4 |
Correct |
24 ms |
19240 KB |
Output is correct |
| 5 |
Correct |
25 ms |
19112 KB |
Output is correct |
| 6 |
Correct |
25 ms |
19064 KB |
Output is correct |
| 7 |
Correct |
38 ms |
19248 KB |
Output is correct |
| 8 |
Correct |
49 ms |
19160 KB |
Output is correct |
| 9 |
Correct |
39 ms |
19144 KB |
Output is correct |
| 10 |
Correct |
91 ms |
19148 KB |
Output is correct |
| 11 |
Correct |
73 ms |
19064 KB |
Output is correct |
| 12 |
Correct |
100 ms |
19192 KB |
Output is correct |
| 13 |
Incorrect |
97 ms |
19232 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
