#include "bits/stdc++.h"
using namespace std;
int n;
vector <int> p;
bool query(vector <int> v) {
vector <int> p (v.size());
for(size_t i = 0; i < v.size(); i++) {
p[v[i]] = i;
}
cout << "query";
for(auto i : p) {
cout << " " << (i+1);
}
cout << endl;
int ans;
cin >> ans;
return ans;
}
vector <int> g[111];
bool vis[111];
void dfs(int x) {
vis[x] = true;
for(auto i : g[x]) {
if(!vis[i]) {
dfs(i);
}
}
}
int mx[111];
int mn[111];
int in[111];
int dp(int x) {
mx[x] = mn[x] = x;
for(auto i : g[x]) {
if(!vis[i]) dp(i);
mx[x] = max(mx[x], mx[i]);
mn[x] = min(mn[x], mn[i]);
}
}
int main(int argc, char const *argv[])
{
cin >> n;
p.resize(n);
for(int i = 0; i < n; i++) {
int x;
cin >> x;
p[x-1] = i;
}
for(int i = n-1; i >= 0; i--) {
memset(vis, false, sizeof vis);
for(int j = i+1; j < n; j++) {
if(vis[p[j]] == false) {
// cout << p[i]+1 << " with " << p[j]+1 << endl;
vector <int> tmp;
for(int k = 0; k < i; k++) {
tmp.emplace_back(p[k]);
}
for(int k = i+1; k <= j; k++) {
if(vis[p[k]] == false) {
tmp.emplace_back(p[k]);
}
}
tmp.emplace_back(p[i]);
for(int k = i+1; k < n; k++) {
if(vis[p[k]] == false && k <= j) continue;
tmp.emplace_back(p[k]);
}
if(query(tmp) == 0) {
g[p[i]].emplace_back(p[j]);
dfs(p[j]);
// cerr << p[i] << ' ' << p[j] << endl;
}
}
}
}
cout << "end" << endl;
memset(vis, false, sizeof vis);
for(int i = 0; i < n; i++) {
if(!vis[i]) {
dp(i);
}
}
typedef pair <int, int> pii;
priority_queue <pii> P;
priority_queue <pii, vector <pii>, greater <pii>> Q;
vector <int> small, big;
memset(in, 0, sizeof in);
for(int i = 0; i < n; i++) {
for(int j : g[i]) {
++in[j];
}
}
for(int i = 0; i < n; i++) {
if(in[i] == 0) {
Q.push(pii(mn[i], i));
P.push(pii(mn[i], i));
}
}
while(!Q.empty()) {
int x = Q.top().second;
Q.pop();
small.push_back(x);
for(int i : g[x]) {
--in[i];
if(in[i] == 0) {
Q.push(pii(mn[i], i));
}
}
}
memset(in, 0, sizeof in);
for(int i = 0; i < n; i++) {
for(int j : g[i]) {
++in[j];
}
}
while(!P.empty()) {
int x = P.top().second;
P.pop();
big.push_back(x);
// cerr << "adding " << x << endl;
for(int i : g[x]) {
--in[i];
if(in[i] == 0) {
P.push(pii(mn[i], i));
}
}
}
vector <int> ans (n);
for(int i = 0; i < n; i++) {
ans[small[i]] = i;
}
for(int i : ans) {
cout << i+1 << ' ';
}
cout << endl;
for(int i = 0; i < n; i++) {
ans[big[i]] = i;
}
for(int i : ans) {
cout << i+1 << ' ';
}
cout << endl;
return 0;
}
Compilation message
zagonetka.cpp: In function 'int dp(int)':
zagonetka.cpp:43:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
308 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
628 KB |
Output is correct |
| 7 |
Correct |
2 ms |
628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
628 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
628 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
