Submission #895857

#	Time	Username	Problem	Language	Result	Execution time	Memory
895857		starchan	Xylophone (JOI18_xylophone)	C++17	47 / 100	46 ms	692 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
void solve(int n)
{
	if(n == 2)
	{
		answer(1, 1);
		answer(2, 2);
		return;
	}
	int l = 1;
	int r = n;
	while(l < r)
	{
		int m = (l+r)/2;
		int t = query(m, n);
		if(t != (n-1))
			r = m;
		else
			l = m+1;
	}
	l--;
	vector<int> d(n+1);
	vector<int> d2(n+1);
	vector<int> a(n+1);
	for(int i = 2; i <= n; i++)
		d[i] = query(i-1, i);
	a[l] = 1;
	if(l >= 2)
		a[l-1] = 1+d[l];
	a[l+1] = 1+d[l+1];
	for(int i = 3; i <= n; i++)
		d2[i] = query(i-2, i);
	for(int i = l+2; i <= n; i++)
	{
		if(d2[i] == (d[i]+d[i-1]))
		{
			if(a[i-2] > a[i-1])
				a[i] = a[i-1]-d[i];
			else
				a[i] = a[i-1]+d[i];
		}
		else
		{
			if(a[i-2] > a[i-1])
				a[i] = a[i-1]+d[i];
			else
				a[i] = a[i-1]-d[i];
		}
	}
	for(int i = l-2; i >= 1; i--)
	{
		//a[i] a[i+1] a[i+2]
		if(d2[i+2] == (d[i+2]+d[i+1]))
		{
			if(a[i+1] < a[i+2])
				a[i] = a[i+1]-d[i+1];
			else
				a[i] = a[i+1]+d[i+1];
		}
		else
		{
			if(a[i+1] < a[i+2])
				a[i] = a[i+1]+d[i+1];
			else
				a[i] = a[i+1]-d[i+1];
		}
	}
	for(int i = 1; i <= n; i++)
		answer(i, a[i]);
	return;
}

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