Submission #421913

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