제출 #1272667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272667		rana_azka	Xylophone (JOI18_xylophone)	C++20	100 / 100	32 ms	1140 KiB

xylophone

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

const int INF = 1e9;
const int MAXN = 5000;

static int A[5000];
int n;
map<pair<int, int>, int> mp;
int konf1[MAXN+5];
int konf2[MAXN+5];
int ans[MAXN+5];

void solve(int N) {
	n = N;
	for(int i = 1; i <= n - 1; i++) mp[{i, i + 1}] = query(i, i+1);
	for(int i = 1; i <= n - 2; i++) mp[{i, i + 2}] = query(i, i+2);

	// KONFIGURASI 1
	bool is_pos = 1;
	konf1[1] = 0; konf1[2] = mp[{1, 2}];
	for(int i = 3; i <= n; i++){
		if(mp[{i-2, i}] != mp[{i-2, i-1}] + mp[{i-1, i}]) is_pos = !is_pos;
		konf1[i] = konf1[i-1] + (is_pos ? mp[{i-1, i}] : -mp[{i-1, i}]);
	}

	int mn = INF, idx_mn = 0;
	int mx =  -INF, idx_mx = 0;
	for(int i = 1; i <= n; i++){
		if(konf1[i] < mn){
			mn = konf1[i];
			idx_mn = i;
		}

		if(konf1[i] > mx){
			mx = konf1[i];
			idx_mx = i;
		}
	}

	if(idx_mn < idx_mx){
		int temp = 1 - mn;
		for(int i = 1; i <= n; i++) ans[i] = konf1[i] + temp;
		for(int i = 1; i <= N; i++) answer(i, ans[i]);
		return ;
	}

	// KONFIGURASI 2
	is_pos = 0;
	konf2[1] = 0; konf2[2] = -mp[{1, 2}];
	for(int i = 3; i <= n; i++){
		if(mp[{i-2, i}] != mp[{i-2, i-1}] + mp[{i-1, i}]) is_pos = !is_pos;
		konf2[i] = konf2[i-1] + (is_pos ? mp[{i-1, i}] : -mp[{i-1, i}]);
	}

	mn = INF, idx_mn = 0;
	mx =  -INF, idx_mx = 0;
	for(int i = 1; i <= n; i++){
		if(konf2[i] < mn){
			mn = konf2[i];
			idx_mn = i;
		}

		if(konf2[i] > mx){
			mx = konf2[i];
			idx_mx = i;
		}
	}

	if(idx_mn < idx_mx){
		int temp = 1 - mn;
		for(int i = 1; i <= n; i++) ans[i] = konf2[i] + temp;
		for(int i = 1; i <= N; i++) answer(i, ans[i]);
		return ;
	}

}

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