Submission #952174

#	Time	Username	Problem	Language	Result	Execution time	Memory
952174		SmuggingSpun	Xylophone (JOI18_xylophone)	C++14	100 / 100	100 ms	936 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
void solve(int n){
	vector<vector<int>>save(n + 1, vector<int>(2));
	for(int i = n; i > 2; i--){
		save[i][0] = query(i - 1, i);
		save[i][1] = query(i - 2, i);
	}
	save[2][0] = query(1, 2);
	for(int I = 1; I <= n; I++){
		vector<bool>used(n + 1, false);
		vector<int>ans(n + 1);
		bool is_ans = used[1] = true;
		if(I > (ans[I] = 1)){
			if(used[ans[I - 1] = save[I][0] + 1]){
				continue;
			}
			used[ans[I - 1]] = true;
			for(int i = I - 2; i > 0; i--){
				if(save[i + 2][0] == save[i + 2][1]){
					if(ans[i + 1] > ans[i + 2]){
						ans[i] = ans[i + 1] - save[i + 1][0];
					}
					else{
						ans[i] = ans[i + 1] + save[i + 1][0];
					}
				}
				else if(save[i + 1][0] == save[i + 2][1]){
					if(ans[i + 1] > ans[i + 2]){
						ans[i] = ans[i + 1] - save[i + 1][0];
					}
					else{
						ans[i] = ans[i + 1] + save[i + 1][0];
					}
				}
				else{
					if(ans[i + 2] > ans[i + 1]){
						ans[i] = ans[i + 2] - save[i + 2][1];
					}
					else{
						ans[i] = ans[i + 2] + save[i + 2][1];
					}
				}
				if(ans[i] < 1 || ans[i] > n || used[ans[i]]){
					is_ans = false;
					break;
				}
				used[ans[i]] = true;
			}
		}
		if(is_ans && I < n){
			if(used[ans[I + 1] = save[I + 1][0] + 1]){
				continue;
			}
			used[ans[I + 1]] = true;
			for(int i = I + 2; i <= n; i++){
				if(save[i - 1][0] == save[i][1]){
					if(ans[i - 1] > ans[i - 2]){
						ans[i] = ans[i - 1] - save[i][0];
					}
					else{
						ans[i] = ans[i - 1] + save[i][0];
					}
				}
				else if(save[i][0] == save[i][1]){
					if(ans[i - 1] > ans[i - 2]){
						ans[i] = ans[i - 1] - save[i][0];
					}
					else{
						ans[i] = ans[i - 1] + save[i][0];
					}
				}
				else{
					if(ans[i - 2] > ans[i - 1]){
						ans[i] = ans[i - 2] - save[i][1];
					}
					else{
						ans[i] = ans[i - 2] + save[i][1];
					}
				}
				if(ans[i] < 1 || ans[i] > n || used[ans[i]]){
					is_ans = false;
					break;
				}
				used[ans[i]] = true;
			}
			if(is_ans){
				for(int i = 1; i <= n; i++){
					answer(i, ans[i]);
				}
				return;
			}
		}
	}
}

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53