Submission #234677

#	Time	Username	Problem	Language	Result	Execution time	Memory
234677		Nodir_Bobiev	Xylophone (JOI18_xylophone)	C++14	47 / 100	78 ms	484 KiB

xylophone

#include "xylophone.h"
int diff2[5555], diff3[5555], ans[5555];

bool please_do_it(int idx, int N){
	ans[idx] = N;
	if( idx != 1 )
		ans[idx-1] = N - diff2[idx-1];
	if( idx != N )
		ans[idx+1] = N - diff2[idx];

	for( int i = idx-2; i >= 1; i -- ){
		int val1 = diff2[i];
		int val2 = diff3[i];
		if( ans[i+1] < ans[i+2] ){
			if( ans[i+2]-ans[i+1] > val1 and val2 == ans[i+2] - ans[i+1]){
				ans[i] = ans[i+1] + val1;
			}
			else if( val2 > val1 ){
				ans[i] = ans[i+1] - val1;
			}
			else{
				ans[i] = ans[i+1] + val1;
			}
		}else{
			if( ans[i+1]-ans[i+2] > val1 and val2 == ans[i+1] - ans[i+2]){
				ans[i] = ans[i+1] - val1;
			}
			else if( val2 > val1 ){
				ans[i] = ans[i+1] + val1;
			}
			else{
				ans[i] = ans[i+1] - val1;
			}
		}
	}
	for( int i = idx+2; i <= N; i ++ ){
		int val1 = diff2[i-1];
		int val2 = diff3[i-2];
		if( ans[i-2] > ans[i-1] ){
			if( ans[i-2] - ans[i-1] > val1 and val2 == ans[i-2] - ans[i-1]){
				ans[i] = ans[i-1] + val1;
			}
			else if( val2 > val1 ){
				ans[i] = ans[i-1] - val1;
			}else{
				ans[i] = ans[i-1] + val1;
			}
		}else{
			if( ans[i-1]-ans[i-2] > val1 and val2 == ans[i-1] - ans[i-2] ){
				ans[i] = ans[i-1] - val1;
			}
			else if( val2 > val1 ){
				ans[i] = ans[i-1] + val1;
			}else{
				ans[i] = ans[i-1] - val1;
			}
		}
	}
	int cnt[5555] = {}, one = false;
	for( int i = 1; i <= N; i ++ ){
		cnt[ans[i]] ++;
		if( cnt[ans[i]]>1 || ans[i] > N || ans[i] < 1){
			return false;
		}
		if( ans[i] == 1 )one = true;
		if( ans[i] == N && !one )return false;
	}
	return true;
}

void solve(int N) {
	for( int i = 1; i <= N-1; i ++ ){
		diff2[i] = query(i, i+1);
	}
	for( int i = 1; i <= N-2; i ++ ){
		diff3[i] = query(i, i + 2 );
	}
	for( int i = 1; i <= N; i ++ ){
		if( please_do_it(i, N) ){
			/*
			for( int i = 1; i <= N; i ++ ){
				printf("%d ", ans[i]);
			}printf("\n");
			*/
			for( int i = 1; i <= N; i ++ ){
				answer(i, ans[i]);
			}
			return;
		}
	}
}

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