#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] ;
ll cnt1[105] ;
ll cnt2[105] ;
vector<pll> edge ;
bool inv[100005] = {} ;
ll 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] ;
bool wrong = 0 ;
void dfs(ll v , ll root)
{
if(check[v]==root)
{
wrong = 1 ;
return ;
}
else if(check[v]!=0) return ;
if(A[v]<low||A[v]>up) return ;
check[v] = root ;
//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 , root) ;
}
}
else
{
if(edge[idx].fi==v)
{
dfs(edge[idx].se , root) ;
}
}
}
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) ;
}
//cout << v << "\n" ;
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" ;
wrong = 0 ;
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] , pos[k]) ;
}
//assert(n==3) ;
assert(up-low+1==topo.size()) ;
for(int k = 1 ; k<= n ; k++) used[k] = A[k] ;
for(int k = low ; k<= up ; k++)
{
//cout << k-low << " " << topo[k-low] << " " << k << "\n" ;
used[topo[topo.size()-1-(k-low)]] = up+low-k ;
}
cout << "query " ;
for(int k = 1 ; k<= n ; k++) cout << used[k] << " " ;
cout << endl ;
int f = 0 ;
cin >> f ;
if(f==0&&!wrong)
{
//cout << pos[i+j] << " " << pos[j] << "\n" ;
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) ;
cnt1[edge[i].fi]++ ;
cnt2[edge[i].se]++ ;
//cout << edge[i].fi << " " << edge[i].se << '\n' ;
}
priority_queue<ll> q1 ;
priority_queue<ll> q ;
for(int i = 1 ; i<= n ; i++)
{
if(cnt2[i]==0) q.push(i) ;
}
ll ti = 0 ;
while(!q.empty())
{
ll x = q.top() ;
q.pop() ;
ti++ ;
val1[x] = ti ;
for(int i = 0 ; i< T1[x].size() ; i++)
{
cnt2[T1[x][i]]-- ;
if(cnt2[T1[x][i]]==0)
{
q.push(T1[x][i]) ;
}
}
}
for(int i = 1 ; i<= n ; i++)
{
if(cnt1[i]==0) q1.push(i) ;
}
ti = 0 ;
while(!q1.empty())
{
ll x = q1.top() ;
q1.pop() ;
ti++ ;
val2[x] = ti ;
//cout << x << "\n" ;
for(int i = 0 ; i< T2[x].size() ; i++)
{
cnt1[T2[x][i]]-- ;
if(cnt1[T2[x][i]]==0)
{
q1.push(T2[x][i]) ;
}
}
}
//for(int i = 0 ; i< n ; i++) cout << topo1[i] << " " ;
//cout << "\n" ;
//for(int i = 0 ; i< n ; i++) cout << topo2[i] << " " ;
//for(int i = 0 ; i< n ; i++) save1[topo1[i]] = i ;
//for(int j = 0 ; j< n ; j++) save2[topo1[j]] = i ;
//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 << n+1-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, long long int)':
zagonetka.cpp:38: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]
38 | for(int i = 0 ; i< T[v].size() ; i++)
| ~^~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk1(long long int, long long int)':
zagonetka.cpp:68: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]
68 | for(int i = 0 ; i < T1[v].size() ; i++)
| ~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk2(long long int, long long int)':
zagonetka.cpp:86: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]
86 | 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:130: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]
130 | assert(up-low+1==topo.size()) ;
| ~~~~~~~~^~~~~~~~~~~~~
zagonetka.cpp:158: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]
158 | for(int i = 0 ; i< edge.size() ; i++)
| ~^~~~~~~~~~~~~
zagonetka.cpp:179:26: 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]
179 | for(int i = 0 ; i< T1[x].size() ; i++)
| ~^~~~~~~~~~~~~~
zagonetka.cpp:200:26: 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]
200 | for(int i = 0 ; i< T2[x].size() ; i++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
0 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
208 KB |
Output is correct |
| 2 |
Correct |
24 ms |
208 KB |
Output is correct |
| 3 |
Correct |
18 ms |
324 KB |
Output is correct |
| 4 |
Correct |
30 ms |
304 KB |
Output is correct |
| 5 |
Correct |
8 ms |
208 KB |
Output is correct |
| 6 |
Correct |
38 ms |
308 KB |
Output is correct |
| 7 |
Correct |
7 ms |
324 KB |
Output is correct |
| 8 |
Correct |
9 ms |
208 KB |
Output is correct |
| 9 |
Correct |
29 ms |
208 KB |
Output is correct |
| 10 |
Correct |
13 ms |
312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
3 ms |
324 KB |
Output is correct |
| 3 |
Correct |
5 ms |
208 KB |
Output is correct |
| 4 |
Correct |
6 ms |
208 KB |
Output is correct |
| 5 |
Correct |
3 ms |
320 KB |
Output is correct |
| 6 |
Correct |
6 ms |
320 KB |
Output is correct |
| 7 |
Correct |
4 ms |
316 KB |
Output is correct |
| 8 |
Correct |
5 ms |
208 KB |
Output is correct |
| 9 |
Correct |
6 ms |
316 KB |
Output is correct |
| 10 |
Correct |
2 ms |
208 KB |
Output is correct |
| 11 |
Correct |
6 ms |
324 KB |
Output is correct |
| 12 |
Correct |
7 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
304 KB |
Output is correct |
| 2 |
Correct |
73 ms |
300 KB |
Output is correct |
| 3 |
Correct |
70 ms |
316 KB |
Output is correct |
| 4 |
Correct |
70 ms |
312 KB |
Output is correct |
| 5 |
Correct |
83 ms |
312 KB |
Output is correct |
| 6 |
Correct |
105 ms |
312 KB |
Output is correct |
| 7 |
Correct |
77 ms |
336 KB |
Output is correct |
| 8 |
Correct |
94 ms |
468 KB |
Output is correct |
| 9 |
Correct |
84 ms |
444 KB |
Output is correct |
| 10 |
Correct |
73 ms |
300 KB |
Output is correct |
| 11 |
Correct |
69 ms |
304 KB |
Output is correct |
| 12 |
Correct |
44 ms |
320 KB |
Output is correct |
| 13 |
Correct |
70 ms |
304 KB |
Output is correct |
| 14 |
Correct |
67 ms |
208 KB |
Output is correct |
| 15 |
Correct |
101 ms |
304 KB |
Output is correct |
| 16 |
Correct |
56 ms |
372 KB |
Output is correct |
