Submission #647290

#	Time	Username	Problem	Language	Result	Execution time	Memory
647290		PoPularPlusPlus	Xylophone (JOI18_xylophone)	C++17	0 / 100	3 ms	208 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

static int A[5000];

int cal(int a , int b , int c){
	return max({a,b,c}) - min({a,b,c});
}

int pre[5002][2];

void solve(int N) {
	if(N == 1){
		answer(1,1);
		return;
	}
	int mid = query(1,N/2);
	int mid1 = query(N/2+1,N);
	for(int i = 1; i < N; i++){
		pre[i][0] = query(i , i + 1);
		if(i + 2 <= N)pre[i][1] = query(i , i + 2);
	}
	int ans[N+1];
	for(int cur = 2; cur <= N; cur++){
		ans[cur] = N;
		if(cur + 1 <= N){
			ans[cur+1] = N - pre[cur][0];
		}
		ans[cur-1] = N - pre[cur-1][0];
		for(int i = cur - 2; i >= 1; i--){
			int val = pre[i][0];
			int case1 = ans[i+1]-val;
			int case2 = ans[i+1]+val;
			if(case2 > N)ans[i] = case1;
			else if(case1 < 1)ans[i] = case2;
			else {
				int val1 =pre[i][1];
				if(case1 >= 1 && cal(case1 , ans[i+1], ans[i+2]) == val1){
					ans[i] = case1;
				}
				else ans[i] = val + ans[i+1];
			}
		}
		for(int i = cur + 2; i <= N; i++){
			int val = pre[i-1][0];
			int case1 = ans[i-1] - val;
			int case2 = ans[i-1] + val;
			if(case2 > N)ans[i] = case1;
			else if(case1 < 1)ans[i] = case2;
			else {
				int val1 = pre[i-2][1];
				if(case1 >= 1 && cal(ans[i-2] , ans[i-1] , case1) == val1){
					ans[i] = case1;
				}
				else ans[i] = ans[i-1] + val;
			}
		}
		bool b = 1;
		for(int i = 1; i <= N; i++){
			if(ans[i] < 1 || ans[i] > N){
				b = 0;
			}
		}
		int mx=0,mn=N;
		for(int i = 1; i <= N/2; i++){
			mx = max(mx , ans[i]);
			mn = min(mn , ans[i]);
		}
		int mx1 = 0 , mn1 = N;
		for(int i = N/2 + 1; i <= N; i++){
			mx1 = max(mx1 , ans[i]);
			mn1 = min(mn1 , ans[i]);
		}
		for(int i = 1; i <= N; i++){
			if(ans[i] == N){
				b = 0;
				break;
			}
			if(ans[i] == 1)break;
		}
		if(b && mid == mx-mn && mid1 == mx1 - mn1)break;
	}
	//for(int i = 1; i <= N; i++)cout << ans[i] << ' ';
	for(int i = 1; i <= N; i++){
		answer(i , ans[i]);
	}
}

Compilation message (stderr)

xylophone.cpp:6:12: warning: 'A' defined but not used [-Wunused-variable]
    6 | static int A[5000];
      |            ^

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