제출 #1290629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290629		opitu	Xylophone (JOI18_xylophone)	C++20	100 / 100	28 ms	452 KiB

xylophone

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

static int A[5000];

void solve(int N) {
	vector<int> diff(N, 0), diff2(N-1, 0);
	for (int i = 1; i < N; ++i) diff[i] = query(i, i+1);
	for (int i = 1; i < N-1; ++i) diff2[i] = query(i, i+2);
	vector<int> sgdf(N, 0); sgdf[1] = 1;
	for (int i = 2; i < N; ++i) sgdf[i] = sgdf[i-1]*(1-2*(diff[i-1]+diff[i] > diff2[i-1]));
	for (int i = 1; i < N; ++i) sgdf[i] = diff[i]*sgdf[i]+sgdf[i-1];
	cout << '\n';
	sgdf[0] = 0;
	int mx = max_element(sgdf.begin(), sgdf.end()) - sgdf.begin(), mn = min_element(sgdf.begin(), sgdf.end()) - sgdf.begin();
	int β, σ;
	if (mx < mn) { σ = -1; β = N+sgdf[mn]; }
	else { σ = 1; β = N-sgdf[mx]; }
	for (int i = 1; i <= N; ++i) answer(i, σ*sgdf[i-1]+β);
}

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