#include <bits/stdc++.h>
using namespace std;
int n;
int query(vector<int> v){
cout << "query";
for (int i = 0; i < n; i++) cout << " " << v[i];
cout << endl << flush;
int result;
cin >> result;
return result;
}
void answer(vector<int> lo, vector<int> hi){
cout << "end" << endl << flush;
for(int i = 0; i < n; i++) cout << lo[i] << " ";
cout << endl << flush;
for(int i = 0; i < n; i++) cout << hi[i] << " ";
cout << endl << flush;
}
int revmap[128];
// u <-- v iff u < v req.
vector<int> g[128]; // No SCC (guaranteed)
vector<int> rg[128]; // Reversed
void dfstopo(int u, int lim, vector<int>& ord, vector<bool>& found){
if(found[u]) return;
found[u] = true;
for(int v : g[u]){
if(v < lim) continue;
dfstopo(v, lim, ord, found);
}
ord.push_back(u);
}
void dfshigher(int u, vector<bool>& found){
if(found[u]) return;
found[u] = true;
for(int v : rg[u]){
dfshigher(v, found);
}
}
void dfsless(int u, int lim, vector<bool>& found){
if(found[u]) return;
found[u] = true;
for(int v : g[u]){
if(v < lim) continue;
dfsless(v, lim, found);
}
}
/**
* Determines whether x < y is a required order or not?
*/
bool customLess(int x, int y){
vector<bool> found;
found.reserve(n+1);
for(int i = 0; i <= n; i++) found.push_back(false);
dfsless(y, x, found);
return found[x];
}
/**
* Get topological ordering (any) with start as source, going down until vertex value less than lim.
*/
vector<int> getTopo(int start, int lim){
vector<int> ord;
vector<bool> found;
found.reserve(n+1);
for(int i = 0; i <= n; i++) found.push_back(false);
dfstopo(start, lim, ord, found);
return ord;
}
vector<int> getLower(int start){
vector<int> ord;
vector<bool> found;
found.reserve(n+1);
for(int i = 0; i <= n; i++) found.push_back(false);
dfsless(start, 0, found);
for(int i = 0; i <= n; i++) if(found[i]) ord.push_back(i);
return ord;
}
vector<int> getHigher(int start){
vector<int> ord;
vector<bool> found;
found.reserve(n+1);
for(int i = 0; i <= n; i++) found.push_back(false);
dfshigher(start, found);
for(int i = n; i >= 0; i--) if(found[i]) ord.push_back(i);
return ord;
}
vector<int> p;
vector<int> minSolve(){
vector<int> pluggedval;
for(int i = 0; i < n; i++) pluggedval.push_back(-1);
int i = 1;
for(int ptr = 0; ptr < n; ptr++){
// Plugging i into p[ptr]
if(pluggedval[ptr] != -1){
continue;
}
vector<int> concern = getLower(p[ptr]);
for(int u : concern){
if(pluggedval[revmap[u]] == -1){
pluggedval[revmap[u]] = i++;
}
}
}
return pluggedval;
}
vector<int> maxSolve(){
vector<int> pluggedval;
for(int i = 0; i < n; i++) pluggedval.push_back(-1);
int i = n;
for(int ptr = 0; ptr < n; ptr++){
// Plugging i into p[ptr]
if(pluggedval[ptr] != -1){
continue;
}
vector<int> concern = getHigher(p[ptr]);
for(int u : concern){
if(pluggedval[revmap[u]] == -1){
pluggedval[revmap[u]] = i--;
}
}
}
return pluggedval;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++){
int x;
cin >> x;
p.push_back(x);
revmap[x] = i;
}
for(int itv = 1; itv <= n; itv++){
for(int i = 1; i+itv <= n; i++){
int j = i+itv;
if(customLess(i, j)){
;// do nothing because i < j already
}else{
vector<int> topo = getTopo(j, i);
int cnt = i;
for(int u : topo){
p[revmap[u]] = cnt++;
}
sort(topo.begin(), topo.end());
for(int k = i; k <= j; k++){
if(!binary_search(topo.begin(), topo.end(), k)){
p[revmap[k]] = cnt++;
}
}
int req = query(p) == 0;
for(int k = i; k <= j; k++){
p[revmap[k]] = k;
}
if(req) g[j].push_back(i);
}
}
}
for(int i = 1; i <= n; i++){
for(int j : g[i]) rg[j].push_back(i);
}
vector<int> lo = minSolve();
vector<int> hi = maxSolve();
answer(lo, hi);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
0 ms |
256 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
256 KB |
Output is correct |
| 2 |
Correct |
30 ms |
256 KB |
Output is correct |
| 3 |
Correct |
35 ms |
256 KB |
Output is correct |
| 4 |
Correct |
38 ms |
256 KB |
Output is correct |
| 5 |
Correct |
8 ms |
256 KB |
Output is correct |
| 6 |
Correct |
38 ms |
256 KB |
Output is correct |
| 7 |
Correct |
5 ms |
256 KB |
Output is correct |
| 8 |
Correct |
8 ms |
256 KB |
Output is correct |
| 9 |
Correct |
35 ms |
256 KB |
Output is correct |
| 10 |
Correct |
21 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
376 KB |
Output is correct |
| 2 |
Correct |
93 ms |
376 KB |
Output is correct |
| 3 |
Correct |
78 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
288 KB |
Output is correct |
| 7 |
Incorrect |
22 ms |
376 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
