This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
bool ask(vector<int> v)
{
cout << "query ";
for(int i : v)
cout << i << ' ';
cout << endl;
bool res;
cin >> res;
return res;
}
void out(vector<int> a, vector<int> b)
{
cout << "end\n";
for(int i : a)
cout << i << ' ';
cout << endl;
for(int i : b)
cout << i << ' ';
cout << endl;
exit(0);
}
vector<int> compute(vector<vector<int> > G)
{
int n = G.size();
int in[n] = {};
for(int i = 0; i < n; i ++)
for(int j : G[i])
in[j]++;
vector<int> topo;
set<int> st;
for(int i = 0; i < n; i ++)
if(in[i] == 0)
st.insert(i);
while(st.size())
{
int u = *st.begin();
st.erase(st.begin());
topo.push_back(u);
for(int v : G[u])
{
in[v]--;
if(in[v] == 0)
st.insert(v);
}
}
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--)
{
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)
{
G[vec.back()].push_back(vec[0]);
I[vec[0]].push_back(vec.back());
// cerr << vec[0] << ' ' << vec.back() << endl;
}
}
}
for(auto [x, y] : conditions)
{
G[x].push_back(y), I[y].push_back(x);
// cerr << x << ' ' << y << endl;
}
vector<int> a = compute(G);
vector<int> b = compute(I);
for(int &i : b)
i = n - i + 1;
out(a, b);
return 0;
}
Compilation message (stderr)
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int j = 0; j + 1 < vec.size(); j++)
| ~~~~~~^~~~~~~~~~~~
zagonetka.cpp:77:8: warning: unused variable 'f' [-Wunused-variable]
77 | bool f[n] = {};
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |