제출 #1267547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267547		trvhung	Xylophone (JOI18_xylophone)	C++20	100 / 100	18 ms	436 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int N = 5e3 + 5;
int a[N];
bool ok[N];

void solve(int n) {
	int l = 1, r = n, L = -1, R = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (query(1, mid) == n - 1) {
			R = mid;
			r = mid - 1;
		} else l = mid + 1;
	}

	l = 1, r = R - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (query(mid, R) == n - 1) {
			L = mid;
			l = mid + 1; 
		} else r = mid - 1;
	}

	ok[1] = ok[n] = 1;
	a[L] = 1, a[R] = n;

	if (L > 1) {
		int v = 1 + query(L - 1, L);
		a[L - 1] = v; ok[v] = 1;
	}
	if (L < n && L + 1 != R) {
		int v = 1 + query(L, L + 1);
		a[L + 1] = v; ok[v] = 1;
	}
	if (R > 1 && a[R - 1] == 0) {
		int v = n - query(R - 1, R);
		a[R - 1] = v; ok[v] = 1;
	} 
	if (R < n) {
		int v = n - query(R, R + 1);
		a[R + 1] = v; ok[v] = 1;
	}

	for (int i = L - 2; i >= 1; --i) {
		int diff = query(i, i + 1);
		if (a[i + 1] + diff > n || ok[a[i + 1] + diff]) {
			a[i] = a[i + 1] - diff;
			ok[a[i]] = 1;
			continue;
		}
		if (a[i + 1] - diff < 1 || ok[a[i + 1] - diff]) {
			a[i] = a[i + 1] + diff;
			ok[a[i]] = 1;
			continue;
		}

		int diff2 = query(i, i + 2);
		if (abs(a[i + 1] - a[i + 2]) == diff2) {
			a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] + diff : a[i + 1] - diff);
			ok[a[i]] = 1;
		} 
		else if (diff + abs(a[i + 1] - a[i + 2]) == diff2) {
			a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] - diff : a[i + 1] + diff);
			ok[a[i]] = 1;
		}
		else {
			int v = a[i + 1] - diff, c = 0;
			if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
				a[i] = v;
				ok[a[i]] = 1;
				c++;
			}

			v = a[i + 1] + diff;
			if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
				a[i] = v;
				ok[a[i]] = 1;
				c++;
			}

			if (c != 1) return cout << c, void();

			assert(c == 1);
		}
	}

	for (int i = R - 2; i > L + 1; --i) {
		int diff = query(i, i + 1);		
		if (a[i + 1] + diff > n || ok[a[i + 1] + diff]) {
			a[i] = a[i + 1] - diff;
			ok[a[i]] = 1;
			continue;
		}
		if (a[i + 1] - diff < 1 || ok[a[i + 1] - diff]) {
			a[i] = a[i + 1] + diff;
			ok[a[i]] = 1;
			continue;
		}

		int diff2 = query(i, i + 2);
		if (abs(a[i + 1] - a[i + 2]) == diff2) {
			a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] + diff : a[i + 1] - diff);
			ok[a[i]] = 1;
		} 
		else if (diff + abs(a[i + 1] - a[i + 2]) == diff2) {
			a[i] = (a[i + 1] < a[i + 2] ? a[i + 1] - diff : a[i + 1] + diff);
			ok[a[i]] = 1;
		}
		else {
			int v = a[i + 1] - diff, c = 0;
			if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
				a[i] = v;
				ok[a[i]] = 1;
				c++;
			}

			v = a[i + 1] + diff;
			if (max({v, a[i + 1], a[i + 2]}) - min({v, a[i + 1], a[i + 2]}) == diff2) {
				a[i] = v;
				ok[a[i]] = 1;
				c++;
			}

			assert(c == 1);
		}
	}

	for (int i = R + 2; i <= n; ++i) {
		int diff = query(i - 1, i);
		if (a[i - 1] + diff > n || ok[a[i - 1] + diff]) {
			a[i] = a[i - 1] - diff;
			ok[a[i]] = 1;
			continue;
		}
		if (a[i - 1] - diff < 1 || ok[a[i - 1] - diff]) {
			a[i] = a[i - 1] + diff;
			ok[a[i]] = 1;
			continue;
		}

		int diff2 = query(i - 2, i);
		if (abs(a[i - 2] - a[i - 1]) == diff2) {
			a[i] = (a[i - 1] < a[i - 2] ? a[i - 1] + diff : a[i - 1] - diff);
			ok[a[i]] = 1;
		} 
		else if (diff + abs(a[i - 2] - a[i - 1]) == diff2) {
			a[i] = (a[i - 1] < a[i - 2] ? a[i - 1] - diff : a[i - 1] + diff);
			ok[a[i]] = 1;
		} 
		else {
			int v = a[i - 1] - diff, c = 0;
			if (max({v, a[i - 1], a[i - 2]}) - min({v, a[i - 1], a[i - 2]}) == diff2) {
				a[i] = v;
				ok[a[i]] = 1;
				c++;
			}

			v = a[i - 1] + diff;
			if (max({v, a[i - 1], a[i - 2]}) - min({v, a[i - 1], a[i - 2]}) == diff2) {
				a[i] = v;
				ok[a[i]] = 1;
				c++;
			}

			assert(c == 1);
		}
	}
for (int i = 1; i <= n; ++i)
		answer(i, a[i]);
}

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