Submission #421941

#	Time	Username	Problem	Language	Result	Execution time	Memory
421941		Nicholas_Patrick	Zagonetka (COI18_zagonetka)	C++17	18 / 100	36 ms	256 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--;
	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 (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: 18 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 51