Submission #421913

#TimeUsernameProblemLanguageResultExecution timeMemory
421913Nicholas_PatrickZagonetka (COI18_zagonetka)C++17
9 / 100
3079 ms328 KiB
#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; //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 (stderr)

zagonetka.cpp: In function 'void answer(const std::vector<int>&, const std::vector<int>&)':
zagonetka.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0; i<x.size(); i++)
      |               ~^~~~~~~~~
zagonetka.cpp:19:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   printf("%d%c", x[i]+1, " \n"[i==x.size()-1]);
      |                                ~^~~~~~~~~~~~
zagonetka.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<y.size(); i++)
      |               ~^~~~~~~~~
zagonetka.cpp:21:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   printf("%d%c", y[i]+1, " \n"[i==y.size()-1]);
      |                                ~^~~~~~~~~~~~
zagonetka.cpp: In function 'bool query(const std::vector<int>&)':
zagonetka.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d", &ret);
      |  ~~~~~^~~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
zagonetka.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d", &i), i--;
      |   ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...