Submission #1324290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324290		adscoding	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	332 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define FORLL(i, a, b) for (ll i = a, _b = b; i <= _b; ++i)
#define FORDLL(i, a, b) for (ll i = a, _b = b; i >= _b; --i)
#define all(x) x.begin(), x.end()
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void __prine_one(const char *&s, const T &x)
{
	while (*s == ' ') ++s;
	const char *p = s;
	int bal = 0;
	while (*s)
	{
		if (*s == '(') ++bal;
		else if (*s == ')') --bal;
		else if (*s == ',' && bal == 0) break;
		++s;
	}
	cerr.write(p, s - p) << " = " << x;
	if (*s == ',')
	{
		cerr << "  ,  ";
		++s;
	}
}

template<typename... Args>
void debug(const char *s, Args... args)
{
	cerr << "[  ";
	int dummy[] = {0, (__prine_one(s, args), 0)...};
	(void)dummy;
	cerr << "  ]\n\n";
}

template<class X>
bool maximize(X &a, const X &b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}

template<class X>
bool minimize(X &a, const X &b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}

// --------------------------------------------------------------------------------------------

const int maxn = 1e5 + 3;
int n, a[maxn], RES[maxn];
bool mark[maxn];

// --------------------------------------------------------------------------------------------

bool valid(int x)
{
	return x >= 1 && x <= n && !mark[x];
}

int get_ans(int root, int so, int delta)
{
	if (root < so)
		return root + delta;
	return root - delta;
}

void solve(int n)
{
	int l = 1, r = n;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (query(mid, n) == n - 1)
			l = mid + 1;
		else
			r = mid - 1;
	}
	int pos1 = r;
	a[pos1] = 1;
	mark[1] = true;
	pii cur = {0, 0};
	if (pos1 < n)
	{
		RES[pos1] = query(pos1, pos1 + 1);
		a[pos1 + 1] = RES[pos1] + 1;
		FOR(i, pos1 + 2, n)
		{
			mark[a[i - 1]] = true;
			RES[i - 1] = query(i - 1, i);
			if (!valid(a[i - 1] + RES[i - 1]))
			{
				a[i] = a[i - 1] - RES[i - 1];
				continue;
			}
			else if (!valid(a[i - 1] - RES[i - 1]))
			{
				a[i] = a[i - 1] + RES[i - 1];
				continue;
			}

			int cur = query(i - 2, i);
			if (cur == RES[i - 1])
				a[i] = get_ans(a[i - 1], a[i - 2], cur);
			else if (cur == RES[i - 2])
				a[i] = get_ans(a[i - 1], a[i - 2], RES[i - 1]);
			else
				a[i] = get_ans(a[i - 2], a[i - 1], cur);
		}
	}
	if (pos1 > 1)
	{
		RES[pos1 - 1] = query(pos1 - 1, pos1);
		a[pos1 - 1] = RES[pos1 - 1] + 1;
		FORD(i, pos1 - 2, 1)
		{
			mark[a[i + 1]] = true;
			RES[i] = query(i, i + 1);
			if (!valid(a[i + 1] + RES[i]))
			{
				a[i] = a[i + 1] - RES[i];
				continue;
			}
			else if (!valid(a[i + 1] - RES[i]))
			{
				a[i] = a[i + 1] + RES[i];
				continue;
			}

			int cur = query(i, i + 2);
			if (cur == RES[i])
				a[i] = get_ans(a[i + 1], a[i + 2], cur);
			else if (cur == RES[i + 1])
				a[i] = get_ans(a[i + 1], a[i + 2], RES[i]);
			else
				a[i] = get_ans(a[i + 2], a[i + 1], cur);
		}
	}

	FOR(i, 1, n)
		answer(i, a[i]);
}

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