Submission #421933

#	Time	Username	Problem	Language	Result	Execution time	Memory
421933		Nicholas_Patrick	Zagonetka (COI18_zagonetka)	C++17	0 / 100	2 ms	200 KiB

zagonetka

#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--;
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			swap(good[i], good[j]);
			bool rec=query(good);
			swap(good[i], good[j]);
			if(not rec){
				if(good[j]<good[i]){
					sort(good.begin(), good.end());
					vector<int> bad(n, -1);
					bad[j]=n-1-j-1;
					bad[i]=n-1-j;
					int ctr=n-1;
					for(int k=0; k<n; k++){
						if(k==i or k==j)
							continue;
						while(ctr==n-1-j-1 or ctr==n-1-j)
							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[j]=j+1;
					good[i]=j;
					int ctr=0;
					for(int k=0; k<n; k++){
						if(k==i or k==j)
							continue;
						while(ctr==j+1 or ctr==j)
							ctr++;
						good[k]=ctr++;
					}
					answer(good, bad);
					return 0;
				}
			}
		}
	}
	// 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--;
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 51