Submission #1097879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097879		ten_xd	Xylophone (JOI18_xylophone)	C++17	100 / 100	45 ms	2904 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int NN = 1e6+54321, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

int A[NN], uz[NN];

void solve(int N)
{
	int poczatek = -1, koniec = N;
	while(koniec - poczatek > 1)
	{
		int srodek = (poczatek + koniec) / 2;
		if(query(srodek+1,N) == N-1) poczatek = srodek;
		else koniec = srodek;
	}

	//cout << "POCZATEK: " << poczatek << endl;

	int idx = poczatek;
	A[idx] = 1, uz[1] = 1;
	if(idx-1 >= 0) A[idx-1] = 1+query(idx-1+1,idx+1), uz[A[idx-1]] = 1;
	if(idx+1 < N) A[idx+1] = 1+query(idx+1,idx+2), uz[A[idx+1]] = 1;

	for(int i = idx+2; i < N; ++i)
	{
		int val = query(i-1+1,i+1), lew = A[i-1]-val, praw = A[i-1]+val;
		//cout << "I: " << i << " VAL: " << val << " LEW: " << lew << " PRAW: " << praw << endl;
		if(lew < 1 or uz[lew]) A[i] = praw, uz[praw] = 1;
		else if(praw > N or uz[praw]) A[i] = lew, uz[lew] = 1;
		else
		{
			//cout << "III: " << i << endl;
			int que = query(i-2+1,i+1);
			if(A[i-2] < lew)
			{
				//cout << "III: " << i << " QUE: " << que << " ROZ: " << lew-A[i-2] << endl;
				if(A[i-2]+que <= A[i-1]) A[i] = lew, uz[lew] = 1;
				else A[i] = praw, uz[praw] = 1;
			}
			else if(A[i-2] > praw)
			{
				if(A[i-2]-que >= A[i-1]) A[i] = praw, uz[praw] = 1;
				else A[i] = lew, uz[lew] = 1;
			}
			else if(A[i-2] > lew and A[i-2] < A[i-1])
			{
				if(que > val) A[i] = praw, uz[praw] = 1;
				else A[i] = lew, uz[lew] = 1;
			}
			else
			{
				if(que > val) A[i] = lew, uz[lew] = 1; 
				else A[i] = praw, uz[praw] = 1;
			}
		}
	}

	//cout << "T" << endl;
	//rep(i,N) cout << A[i] << endl;
	//cout << endl;

	for(int i = idx-2; i >= 0; --i)
	{
		int val = query(i+1,i+1+1), lew = A[i+1]-val, praw = A[i+1]+val;
		//cout << "I: " << i << " VAL: " << val << " LEW: " << lew << " PRAW: " << praw << endl;
		if(lew < 1 or uz[lew]) A[i] = praw, uz[praw] = 1;
		else if(praw > N or uz[praw]) A[i] = lew, uz[lew] = 1;
		else
		{
			//cout << "III: " << i << endl;
			int que = query(i+1,i+2+1);
			if(A[i+2] < lew)
			{
				//cout << "III: " << i << " QUE: " << que << " ROZ: " << lew-A[i-2] << endl;
				if(A[i+2]+que <= A[i+1]) A[i] = lew, uz[lew] = 1;
				else A[i] = praw, uz[praw] = 1;
			}
			else if(A[i+2] > praw)
			{
				if(A[i+2]-que >= A[i+1]) A[i] = praw, uz[praw] = 1;
				else A[i] = lew, uz[lew] = 1;
			}
			else if(A[i+2] > lew and A[i+2] < A[i+1])
			{
				if(que > val) A[i] = praw, uz[praw] = 1;
				else A[i] = lew, uz[lew] = 1;
			}
			else
			{
				if(que > val) A[i] = lew, uz[lew] = 1; 
				else A[i] = praw, uz[praw] = 1;
			}
		}
	}

	//cout << "T" << '\n';
	//cout << endl;
	//rep(i,N) cout << A[i] << endl;
	//cout << endl;

	rep(i,N) answer(i+1,A[i]);

}

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