#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ld double
#define cd complex<ld>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std ;
ll A[105] ;
ll pos[105] ;
vector<pll> edge ;
bool inv[100005] = {} ;
bool check[105] = {} ;
vector<ll> T[105] ;
ll low = 0 , up = 0 ;
vector<ll> topo , topo1 , topo2 ;
ll used[105] ;
vector<ll> T1[105] , T2[105] ;
ll val1[105] , val2[105] ;
void dfs(ll v)
{
if(check[v]) return ;
if(A[v]<low||A[v]>up) return ;
check[v] = 1 ;
//cout << v << "\n" ;
for(int i = 0 ; i< T[v].size() ; i++)
{
ll idx = T[v][i] ;
if(inv[idx])
{
if(edge[idx].se==v)
{
dfs(edge[idx].fi) ;
}
}
else
{
if(edge[idx].fi==v)
{
dfs(edge[idx].se) ;
}
}
}
topo.push_back(v) ;
}
void dfsk1(ll v , ll le)
{
if(check[v])
{
return ;
}
else
{
check[v] = 1 ;
val1[v] = 1 ;
for(int i = 0 ; i < T1[v].size() ; i++)
{
dfsk1(T1[v][i] , le) ;
val1[v] = max(val1[v] , val1[T1[v][i]]+1) ;
}
topo1.push_back(v) ;
}
}
void dfsk2(ll v , ll le)
{
if(check[v])
{
return ;
}
else
{
check[v] = 1 ;
val2[v] = 1 ;
for(int i = 0 ; i < T2[v].size() ; i++)
{
dfsk2(T2[v][i] , le) ;
val2[v] = max(val2[v] , val2[T2[v][i]]+1) ;
}
topo2.push_back(v) ;
}
}
void solve()
{
ll n ;
cin >> n ;
//assert(n==2) ;
for(int i = 1 ; i <= n ; i++)
{
cin >> A[i] ;
pos[A[i]] = i ;
}
//assert(n==3) ;
for(int i = 1 ; i < n ; i++)
{
for(int j = 1 ; j<= n-i ; j++)
{
//if(i!=1) break ;
//cout << i+j << " " << i << " " << pos[i+j] << " " << pos[i] << "\n" ;
//cout << j << " " << i +j << "\n" ;
for(int k = 1 ; k<= n ; k++)
{
check[k] = 0 ;
}
edge.push_back({pos[i+j] , pos[j]}) ;
inv[edge.size()-1] = 1 ;
topo.clear() ;
T[pos[i+j]].push_back(edge.size()-1) ;
T[pos[j]].push_back(edge.size()-1) ;
low = j ; up = i+j ;
for(int k = low ; k<= up ; k++)
{
//cout << pos[k] << "-1\n" ;
dfs(pos[k]) ;
}
//assert(n==3) ;
assert(up-low+1==topo.size()) ;
for(int k = 1 ; k<= n ; k++) used[k] = pos[k] ;
for(int k = low ; k<= up ; k++)
{
//cout << k-low << "\n" ;
used[topo[k-low]] = k ;
}
cout << "query " ;
for(int k = 1 ; k<= n ; k++) cout << used[k] << " " ;
cout << endl ;
int f = 0 ;
cin >> f ;
if(f==0)
{
inv[edge.size()-1] = 0 ;
}
else
{
//assert(n==3) ;
edge.pop_back() ;
T[pos[i+j]].pop_back() ;
T[pos[j]].pop_back() ;
//assert(n==3) ;
}
}
}
//assert(n==3) ;
for(int i = 0 ; i< edge.size() ; i++)
{
T1[edge[i].fi].push_back(edge[i].se) ;
T2[edge[i].se].push_back(edge[i].fi) ;
}
//for(int i = 0 ; i< edge.size() ; i++) cout << edge[i].fi << " " << edge[i].se << "\n" ;
for(int j = 1 ; j<= n ; j++) check[j] = 0 ;
for(int i = 1 ; i<= n ; i++)
{
dfsk1(i , 0) ;
}
for(int j = 1 ; j<= n ; j++) check[j] = 0 ;
for(int i = 1 ; i<= n ; i++)
{
dfsk2(i , 0) ;
}
for(int i = 0 ; i< n; i ++) val1[topo1[i]] = i+1 ;
for(int i = 0 ; i< n ; i++) val2[topo2[i]] = n-i;
cout << "end" << endl ;
for(int i = 1 ; i<= n ; i++) cout << val1[i] << " " ;
cout << endl ;
for(int j = 1 ; j<= n ; j++) cout << val2[j] << " " ;
cout << endl ;
}
signed main()
{
//ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
//freopen("IN.txt","r",stdin) ;
//freopen("LINES.inp" , "r" , stdin) ;
//freopen("LINES.out" , "w" , stdout) ;
//freopen("OUT.txt" , "w" , stdout) ;
int t = 1 ;
//cout << t << " " << n << "\n" ;
for(int i = 1 ; i<= t ; i++)
{
solve();
}
}
Compilation message
zagonetka.cpp: In function 'void dfs(long long int)':
zagonetka.cpp:30:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0 ; i< T[v].size() ; i++)
| ~^~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk1(long long int, long long int)':
zagonetka.cpp:60:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0 ; i < T1[v].size() ; i++)
| ~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk2(long long int, long long int)':
zagonetka.cpp:78:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0 ; i < T2[v].size() ; i++)
| ~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from zagonetka.cpp:1:
zagonetka.cpp: In function 'void solve()':
zagonetka.cpp:120:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | assert(up-low+1==topo.size()) ;
| ~~~~~~~~^~~~~~~~~~~~~
zagonetka.cpp:147:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i = 0 ; i< edge.size() ; i++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
208 KB |
Execution killed with signal 13 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
208 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
208 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
208 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
