Submission #58565

#	Time	Username	Problem	Language	Result	Execution time	Memory
58565		YaDon4ick	Xylophone (JOI18_xylophone)	C++14	47 / 100	110 ms	584 KiB

xylophone

//By Don4ick
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
#include "xylophone.h"


typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

using namespace std;


void solve(int n) {
	int pos = -1;
	//~binary_search
	{
		int l = 0, r = n + 1;
		while(l < r - 1)
		{
			int mid = (l + r) >> 1;
			if (query(mid, n) == n - 1)
				l = mid;
			else
				r = mid;			
		}
		pos = l;
	}
	answer(pos, 1);
	//~solve(1, pos)
	if (pos > 1)
	{	
		int y = 1, x = query(pos - 1, pos) + 1;
		answer(pos - 1, x);
		for (int i = pos - 2; i >= 1; i--)
		{
			int value = query(i, i + 2);
			if (value > abs(x - y))
			{
				int newValue = query(i, i + 1);
				if (x < y)
				{
					if (newValue == value)
					{
						y = x + value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x - newValue;
						swap(x, y);
						answer(i, x);
					}
				}				
				else
				{
					if (newValue == value)
					{
						y = x - value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x + newValue;
						swap(x, y);
						answer(i, x);
					}
				}
			}
			else
			{
				int newValue = query(i, i + 1);			
				if (x < y)
				{
					y = x + newValue;
					swap(x, y);
					answer(i, x);	
				}
				else
				{
					y = x - newValue;
					swap(x, y);
					answer(i, x);
				}
			}
		} 
	}
	//~solve(pos, n)
	if (pos < n)
	{
		int y = 1, x = query(pos, pos + 1) + 1;
		answer(pos + 1, x);		
		for (int i = pos + 2; i <= n; i++)
		{
			int value = query(i - 2, i);
			if (value > abs(x - y))
			{
				int newValue = query(i - 1, i);
				if (x < y)
				{
					if (newValue == value)
					{
						y = x + value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x - newValue;
						swap(x, y);
						answer(i, x);
					}
				}				
				else
				{
					if (newValue == value)
					{
						y = x - value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x + newValue;
						swap(x, y);
						answer(i, x);
					}
				}
			}
			else
			{
				int newValue = query(i - 1, i);			
				if (x < y)
				{
					y = x + newValue;
					swap(x, y);
					answer(i, x);	
				}
				else
				{
					y = x - newValue;
					swap(x, y);
					answer(i, x);
				}
			}
		}
	}
}

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