| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 421941 | 2021-06-09T14:00:10 Z | Nicholas_Patrick | Zagonetka (COI18_zagonetka) | C++17 | 36 ms | 256 KB |
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
bool query(const vector<int>& x){
printf("query");
for(int i : x)
printf(" %d", i+1);
printf("\n");
fflush(stdout);
int ret;
scanf("%d", &ret);
return ret;
}
void answer(const vector<int>& x, const vector<int>& y){
printf("end\n");
for(int i=0; i<x.size(); i++)
printf("%d%c", x[i]+1, " \n"[i==x.size()-1]);
for(int i=0; i<y.size(); i++)
printf("%d%c", y[i]+1, " \n"[i==y.size()-1]);
fflush(stdout);
}
int main(){
int n;
scanf("%d", &n);
vector<int> good(n);
for(int& i : good)
scanf("%d", &i), i--;
vector<int> inverse(n);
for(int i=0; i<n; i++)
inverse[good[i]]=i;
for(int k=1; k<n; k++)for(int i=0; i<n; i++){
int j=i-k;
if(j<0)
continue;
int x=inverse[j], y=inverse[i];
if(x<y)swap(x, y);
swap(good[x], good[y]);
bool rec=query(good);
swap(good[x], good[y]);
if(not rec){
if(good[y]<good[x]){
sort(good.begin(), good.end());
vector<int> bad(n, -1);
bad[y]=n-1-y-1;
bad[x]=n-1-y;
int ctr=n-1;
for(int k=0; k<n; k++){
if(k==x or k==y)
continue;
while(ctr==n-1-y-1 or ctr==n-1-y)
ctr--;
bad[k]=ctr--;
}
answer(good, bad);
return 0;
}else{
auto bad=good;
sort(bad.rbegin(), bad.rend());
fill(good.begin(), good.end(), -1);
good[y]=y+1;
good[x]=y;
int ctr=0;
for(int k=0; k<n; k++){
if(k==x or k==y)
continue;
while(ctr==y+1 or ctr==y)
ctr++;
good[k]=ctr++;
}
answer(good, bad);
return 0;
}
}
}
// //inverted indexing
// vector<vector<vector<int>>> testVectors(n);
// vector<vector<int>> testResults(n);//true --> no conditions
// //regular indexing
// vector<vector<int>> conditions(n);//true --> conditions
// for(int i=0; i<n; i++){
// testVectors[i].resize(i);
// testResults[i].resize(i);
// conditions[i].resize(i);
// }
// for(int k=1; k<n; k++)for(int i=n; i--;){
// int j=i-k;
// if(j<0)
// break;
// vector<int> vect;
// auto& resu=testResults[i][j];
// resu=true;
// bool tested=false;
// if(not tested){
// vect=good;
// bool cantest=true;
// for(int l=j+1; l<i; l++){
// if(not testResults[l][j]){
// cantest=false;
// break;
// }
// }
// if(cantest){
// for(int l=j; l<i; l++)
// swap(vect[inverse[j]], vect[inverse[l+1]]);
// resu=query(vect);
// tested=true;
// }
// }
// if(not tested){
// vect=good;
// bool cantest=true;
// for(int l=j+1; l<i; l++){
// if(not testResults[i][l]){
// cantest=false;
// break;
// }
// }
// if(cantest){
// for(int l=i-1; l>=j; l--)
// swap(vect[inverse[i]], vect[inverse[l]]);
// resu=query(vect);
// tested=true;
// }
// }
// if(not tested)
// resu=false;
// int x=max(inverse[i], inverse[j]), y=min(inverse[i], inverse[j]);
// conditions[x][y]=not resu;
// }
// vector<int> low(n), hig(n);
// for(int i=n; i--;){
// low[i]=i;
// hig[i]=n-1-i;
// }
// for(;;){
// bool satisfied=true;
// for(int i=n; i--;)for(int j=i; j--;){
// if(conditions[i][j] and (low[i]<low[j])!=(good[i]<good[j])){
// satisfied=false;
// break;
// }
// }
// if(satisfied)
// break;
// next_permutation(low.begin(), low.end());
// }
// for(;;){
// bool satisfied=true;
// for(int i=n; i--;)for(int j=i; j--;){
// if(conditions[i][j] and (hig[i]<hig[j])!=(good[i]<good[j])){
// satisfied=false;
// break;
// }
// }
// if(satisfied)
// break;
// prev_permutation(hig.begin(), hig.end());
// }
// answer(low, hig);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 200 KB | Output is correct |
| 2 | Incorrect | 0 ms | 200 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 200 KB | Output is correct |
| 2 | Correct | 5 ms | 200 KB | Output is correct |
| 3 | Correct | 33 ms | 200 KB | Output is correct |
| 4 | Correct | 36 ms | 200 KB | Output is correct |
| 5 | Correct | 9 ms | 200 KB | Output is correct |
| 6 | Correct | 31 ms | 200 KB | Output is correct |
| 7 | Correct | 5 ms | 200 KB | Output is correct |
| 8 | Correct | 1 ms | 200 KB | Output is correct |
| 9 | Correct | 12 ms | 200 KB | Output is correct |
| 10 | Correct | 8 ms | 200 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 256 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 13 ms | 200 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |