Submission #1272911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272911		choed	Xylophone (JOI18_xylophone)	C++20	100 / 100	28 ms	520 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define plll pair<ll,pll>

static int A[5000];

void solve(int N) {

	// int value = query(1, N);
	
	ll diff[N];
	for(int i=1; i<N; i++)
		diff[i]=query(i,i+1);

	if(N==2){
		answer(1, 1);
		answer(2, 2);
		return;
	}
	
	ll konfig[N+1][2]; // 0 itu awalnya +, 1 awalnya -
	memset(konfig,0,sizeof(konfig));
	ll val = query(1, 3);
	if(val == diff[1] + diff[2]){
		konfig[1][0] = 1;
		konfig[2][0] = 1;
		konfig[1][1] = -1;
		konfig[2][1] = -1;
	}else{
		konfig[1][0] = 1;
		konfig[2][0] = -1;
		konfig[1][1] = -1;
		konfig[2][1] = 1;
	}

	// cari konfig yang mungkin ---------------------------------------------
	for(int i=3; i<N; i++){
		val=query(i-1, i+1);
		if(val==diff[i-1]+diff[i]){
			if(konfig[i-1][0]>0){
				konfig[i][0]=1;
				konfig[i][1]=-1;
			}else{
				konfig[i][0]=-1;
				konfig[i][1]=1;
			}
		}else{
			if(konfig[i-1][0]>0){
				konfig[i][0]=-1;
				konfig[i][1]=1;
			}else{
				konfig[i][0]=1;
				konfig[i][1]=-1;
			}
		}
	}
	
	ll sum=0;
	ll mn=0, mnidx=0;
	ll mx=0, mxidx=0;
	ll ans[N+1];

	// cek kevalid-an konfig pertama dulu ---------------------------------
	for(int i=1; i<N; i++){
		sum+=konfig[i][0]*diff[i];
		if(sum<mn){
			mn=sum;
			mnidx=i;
		}
		if(sum>mx){
			mx=sum;
			mxidx=i;
		}
	}

	if(mnidx<mxidx){
		sum=1;
		ans[mnidx+1]=1;
		for(int i=mnidx; i>=1; i--){
			sum -= konfig[i][0]*diff[i];
			ans[i] =  sum;
		}

		sum=1;
		for(int i=mnidx+1; i<N; i++){
			sum += konfig[i][0]*diff[i];
			ans[i+1] = sum;
		}
		goto done;
	}

	// cek konfig kedua -------------------------------------------------
	sum=0;
	mn=mnidx=0;
	mx=mxidx=0;
	for(int i=1; i<N; i++){
		sum+=konfig[i][1]*diff[i];
		if(sum<mn){
			mn=sum;
			mnidx=i;
		}
		if(sum>mx){
			mx=sum;
			mxidx=i;
		}
	}

	if(mnidx<mxidx){
		sum=1;
		ans[mnidx+1]=1;
		for(int i=mnidx; i>=1; i--){
			sum -= konfig[i][1]*diff[i];
			ans[i] = sum;
		}

		sum=1;
		for(int i=mnidx+1; i<N; i++){
			sum += konfig[i][1]*diff[i];
			ans[i+1] = sum;
		}
	}

	// -----------------------------------------------------------------

	done:
	for(int i = 1; i <= N; i++) {
		answer(i, ans[i]);
	}
}

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