제출 #421893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421893		Nicholas_Patrick	Zagonetka (COI18_zagonetka)	C++17	0 / 100	3069 ms	1996 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;
		auto& vect=testVectors[i][j];
		auto& resu=testResults[i][j];
		if(j+1==i){
			vect=good;
			swap(vect[inverse[j]], vect[inverse[i]]);
			resu=query(vect);
		}else{
			if(testResults[i][j+1]){
				vect=testVectors[i][j+1];
				swap(vect[inverse[j]], vect[inverse[i]]);
				resu=query(vect);
			}else if(testResults[i-1][j]){
				vect=testVectors[i-1][j];
				swap(vect[inverse[j]], vect[inverse[i]]);
				resu=query(vect);
			}else{
				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);
}

컴파일 시 표준 에러 (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