#include<bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for(int i = 0; i + 1 < v.size(); i++)
cout << v[i] << ' ';
cout << v.back() << endl;
}
bool ask(vector<int> v)
{
cout << "query ";
print(v);
bool res;
cin >> res;
return res;
}
void out(vector<int> a, vector<int> b)
{
cout << "end\n";
print(a);
print(b);
exit(0);
}
vector<int> compute(vector<vector<int> > G, int m)
{
int n = G.size();
int in[n] = {};
for(int i = 0; i < n; i ++)
for(int j : G[i])
{
// cerr << i << ' ' << j << endl;
in[j]++;
}
vector<int> topo;
set<int> st;
for(int i = 0; i < n; i ++)
if(in[i] == 0)
st.insert(i * m);
while(st.size())
{
int u = *st.begin();
//cerr << u << endl;
u *= m;
st.erase(st.begin());
topo.push_back(u);
for(int v : G[u])
{
in[v]--;
if(in[v] == 0)
st.insert(v * m);
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++)
ans[topo[i]] = i + 1;
return ans;
}
int main()
{
int n;
cin >> n;
vector<int> p(n), idx(n + 1);
for(int i = 0; i < n; i ++)
{
cin >> p[i];
idx[p[i]] = i;
}
vector<vector<int> > G(n), I(n);
vector<pair<int,int> > conditions;
bool f[n] = {};
for(int v = 1; v <= n; v++)
{
vector<int> vec = {idx[v]};
for(int u = v - 1; u > 0; u--)
{
swap(p[idx[v]], p[idx[u]]);
bool res = ask(p);
if(!res)
G[idx[u]].push_back(idx[v]);
swap(p[idx[v]], p[idx[u]]);
/* vector<int> q = p;
vec.push_back(idx[u]);
for(int j = 0; j + 1 < vec.size(); j++)
swap(q[vec[j]], q[vec[j + 1]]);
int cur = vec.back();
while(G[cur].size())
{
// cerr << "cur = " << cur << endl;
int i = G[cur][0];
for(int k : G[cur])
if(q[i] < q[k])
i = k;
swap(q[i], q[cur]);
cur = i;
}
bool res = ask(q);
if(!res)
{
conditions.push_back({vec.back(), vec[0]});
G[vec.back()].push_back(vec[0]);
I[vec[0]].push_back(vec.back());
// cerr << vec[0] << ' ' << vec.back() << endl;
}
vec.pop_back(); */
}
}
/*
for(auto [x, y] : conditions)
{
// G[x].push_back(y), I[y].push_back(x);
cerr << x << ' ' << y << endl;
}
// */
vector<int> a = compute(G, 1);
vector<int> b = compute(G, -1);
out(a, b);
return 0;
}
Compilation message
zagonetka.cpp: In function 'void print(std::vector<int>)':
zagonetka.cpp:7:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | for(int i = 0; i + 1 < v.size(); i++)
| ~~~~~~^~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:83:8: warning: unused variable 'f' [-Wunused-variable]
83 | bool f[n] = {};
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
