제출 #1290659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290659		mhaer	Xylophone (JOI18_xylophone)	C++20	100 / 100	27 ms	468 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define ll long long
// #define Fin(a) cout << #a << " "; for (int& i : a) {cout << i << " ";}cout << "\n";
using namespace std;
static int A[5000];

set<int> found;

void solve(int N) {

	vector<int> fark1(N);
	vector<int> fark2(N-1);

	for (int i = 1;i <= N-1;i++) {
		fark1[i] = query(i, i+1);
	}

	for (int i = 1;i <= N-2;i++) {
		fark2[i] = query(i, i+2);
	}

	vector<bool> direction(N);
	for (int i = 1;i <= N-2;i++) {
		direction[i+1] = direction[i];
		if (fark2[i] != (fark1[i] + fark1[i+1])) {
		    direction[i+1] = !direction[i+1];
		}
	}

	vector<int> pref(N);

	// for (bool i : direction) {
	// 	cout << i << " ";
	// }
	// cout << "\n";
	for (int i = 1;i < N;i++) {
		fark1[i] *= (direction[i] == 1 ? (-1) : 1);
	}
	// cout << "a ";
	// 	for (int i : fark1) cout << i << " ";
	// cout << "\n";

	for (int i = 1;i <N;i++) {
		pref[i] = pref[i-1] + fark1[i];
	}






	int min_ = 0;
	int max_ = 0;
	for (int i = 0;i < N;i++) {
		if (pref[i] > pref[max_]) {
			max_ = i;
		}
		if (pref[i] < pref[min_]) {
			min_ = i;
		}
	}

	int c = pref[max_];

	for (int& i : pref) i -= (c - N);

	if (min_ > max_) {
		// cout << "Yeah\n";
		for (int& i : pref) i = N-i+1;
	}

	// cout << "bbb ";
	// for (int i : pref) cout << i << " ";
	// cout << "\n";
	// for (int i : direction) cout << i << " ";
	// cout << "\n";



	for (int i = 0;i < N;i++) {
		// cout << "At " << i << "\n";
		answer(i+1, pref[i]);
	}



	// for (int i : pref) cout << i << " ";
	// cout << "\n";

}

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