Submission #1272242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272242		warrenn	Xylophone (JOI18_xylophone)	C++20	11 / 100	3 ms	1400 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;

static int a[5000];
int val[502][502];
bool ganti[502];
int diff[502];
int ans[502];

void solve(int n) {
	for(int q=2;q<=n;q++){
		val[q-1][q]=query(q-1,q);
		diff[q]=val[q-1][q];
	}
	for(int q=3;q<=n;q++){
		val[q-2][q]=query(q-2,q);
	}

	for(int q=3;q<=n;q++){
		if(val[q-2][q-1]+val[q-1][q]==val[q-2][q]){

		}
		else{
			ganti[q]=true;
		}
		
	}

	// awal ga usah ganti
	for(int q=3;q<=n;q++){
		if(ganti[q]){
			if(diff[q-1]>0){
				diff[q]=-diff[q];
			}
		}
		else{
			if(diff[q-1]<0){
				diff[q]=-diff[q];
			}
		}
	}
	int pref[n+1];
	pref[1]=0;
	int mn=0;
	int idxmn=1;
	int mx=0;
	int idxmx=1;

	for(int q=2;q<=n;q++){
		pref[q]=pref[q-1]+diff[q];
		if(pref[q]<mn){
			mn=pref[q];
			idxmn=q;
		}
		if(pref[q]>mx){
			mx=pref[q];
			idxmx=q;
		}
	}
	

	if(idxmn>idxmx){
		swap(idxmn,idxmx);
		for(int q=2;q<=n;q++){
			diff[q]=-diff[q];
		}
	}

	ans[idxmn]=1;
	for(int q=idxmn;q>=2;q--){
		ans[q-1]=ans[q]-diff[q];
	}
	for(int q=idxmn+1;q<=n;q++){
		ans[q]=ans[q-1]+diff[q];
	}

	for(int q=1;q<=n;q++){
		answer(q,ans[q]);
	}
}

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