Submission #722035

#	Time	Username	Problem	Language	Result	Execution time	Memory
722035		FatihSolak	Xylophone (JOI18_xylophone)	C++17	100 / 100	73 ms	436 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int A[5005];
bool vis[5005];
void solve(int N) {

	int l = 1,r = N;
	while(l < r){
		int m = (l + r)/2;
		if(query(1,m) != N-1){
			l = m+1;
		}
		else r = m;
	}
	A[l] = N;
	vis[N] = 1;
	answer(l,N);
	for(int i = l-1; i>=1; i--){
		int dif = query(i,i+1);
		if(A[i+1] + dif > N || vis[A[i+1] + dif]){
			A[i] = A[i+1] - dif;
			vis[A[i]] = 1;
			answer(i,A[i]);
			continue;
		}
		if(A[i+1] - dif < 1 || vis[A[i+1] - dif]){
			A[i] = A[i+1] + dif;
			vis[A[i]] = 1;
			answer(i,A[i]);
			continue;
		}
		for(int j = i + 1;j<=l;j++){
			if(A[j] > A[i+1] + dif){
				int val = query(i,j);
				if(val == A[j] - (A[i+1] - dif)){
					A[i] = (A[i+1] - dif);
				}
				else A[i] = (A[i+1] + dif);
				break;
			}
			if(A[j] < A[i+1] - dif){
				int val = query(i,j);
				if(val == (A[i+1] + dif) - A[j]){
					A[i] = (A[i+1] + dif);
				}
				else A[i] = (A[i+1] - dif);
				break;
			}
		}
		vis[A[i]] = 1;
		answer(i,A[i]);
	}
	for(int i = l+1; i<=N; i++){
		int dif = query(i-1,i);
		if(A[i-1] + dif > N || vis[A[i-1] + dif]){
			A[i] = A[i-1] - dif;
			vis[A[i]] = 1;
			answer(i,A[i]);
			continue;
		}
		if(A[i-1] - dif < 1 || vis[A[i-1] - dif]){
			A[i] = A[i-1] + dif;
			vis[A[i]] = 1;
			answer(i,A[i]);
			continue;
		}
		for(int j = i -1;j>=l;j--){
			if(A[j] > A[i-1] + dif){
				int val = query(j,i);
				if(val == A[j] - (A[i-1] - dif)){
					A[i] = (A[i-1] - dif);
				}
				else A[i] = (A[i-1] + dif);
				break;
			}
			if(A[j] < A[i-1] - dif){
				int val = query(j,i);
				if(val == (A[i-1] + dif) - A[j]){
					A[i] = (A[i-1] + dif);
				}
				else A[i] = (A[i-1] - dif);
				break;
			}
		}
		vis[A[i]] = 1;
		answer(i,A[i]);
	}
}

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