Submission #1194570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194570		a0ms1n	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	416 KiB

xylophone

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

static int A[5005];

int diff[5005]={0},sdiff[5005]={0};

/*

diff[x] = query(x,x+1);

if query(x,x+2) != diff[x]+diff[x+1]

*/

void solve(int n) {
	int cur_diff = 0;
	int sign = 1;
	int mi=0,mx=0,mxp=0,mip=0;
	sdiff[1] = diff[1] = query(1,2);
	int sum = sdiff[1];
	if(sum>mx)mxp=1,mx=sum;
	if(sum<mi)mip=1,mi=sum;
	for(int i=1;i<=n-2;i++){
		cur_diff = query(i,i+2);
		diff[i+1]=query(i+1,i+2);
		if(diff[i]+diff[i+1]!=cur_diff){
			sign *= -1;
		}
		sdiff[i+1] = sign*diff[i+1];
		sum += sdiff[i+1];
		if(sum>mx)mxp=i+1,mx=sum;
		if(sum<mi)mip=i+1,mi=sum;
	}
	int cur;
	if(mxp<=mip){
		cur = 1+mx;
		for(int i=1;i<=n-1;i++){
			answer(i,cur);
			cur += -sdiff[i];
		}
		answer(n,cur);
	}
	else{
		cur = 1+mi;
		for(int i=1;i<=n-1;i++){
			answer(i,cur);
			cur += sdiff[i];
		}
		answer(n,cur);
	}
	

}

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