제출 #210316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210316		Seanliu	Xylophone (JOI18_xylophone)	C++14	100 / 100	103 ms	504 KiB

xylophone

#include <iostream>
#include "xylophone.h"
using namespace std;

const int maxN = 6e3 + 226;

int val[maxN], q1[maxN], q2[maxN], a, b, c, minAt, maxAt, ans[maxN];

void solve(int N){
	int a, b, c;
	for(int i = 1; i < N; i++){
		q1[i] = query(i, i + 1);
	}
	for(int i = 1; i < N - 1; i++){
		q2[i] = query(i, i + 2);
	}
	val[2] = q1[1];
	for(int i = 3; i <= N; i++){
		a = q1[i - 2], b = q1[i - 1], c = q2[i - 2];
		if(a + b == c){
			if(val[i - 1] > 0) val[i] = b;
			else val[i] = -b;
		} else {
			if(val[i - 1] > 0) val[i] = -b;
			else val[i] = b;
		}
	}
	minAt = maxAt = 1;
	for(int i = 1; i <= N; i++){
		ans[i] = val[i] + ans[i - 1];
		if(ans[minAt] > ans[i]) minAt = i;
		if(ans[maxAt] < ans[i]) maxAt = i;
	}
	if(minAt < maxAt){
		for(int i = 1; i <= N; i++) answer(i, ans[i] - ans[minAt] + 1);
		return;
	}
	minAt = maxAt = 1;
	for(int i = 1; i <= N; i++){
		ans[i] = -val[i] + ans[i - 1];
		if(ans[minAt] > ans[i]) minAt = i;
		if(ans[maxAt] < ans[i]) maxAt = i;
	}
	for(int i = 1; i <= N; i++) answer(i, ans[i] - ans[minAt] + 1);
}

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