제출 #1194583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194583		a0ms1n	Xylophone (JOI18_xylophone)	C++20	100 / 100	26 ms	456 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: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53