Submission #71668

#	Time	Username	Problem	Language	Result	Execution time	Memory
71668		jibu11	Xylophone (JOI18_xylophone)	C++14	0 / 100	4 ms	644 KiB

xylophone

#include "xylophone.h"

//static int A[5000];
int lis[5010], vis[5010];

int bs(int in, int fin, int vl)
{
	if(in >= fin)
		return in;
	int med = (in+fin)/2;
	if(query(1,med) == vl)
		return bs(in, med, vl);
	return bs(med+1, fin, vl);
}

int abs(int a)
{
	return a > 0 ? a : -a;
}

void coisoetal(int pos, int dir, int N)
{
	int i;
	for(i = pos+2*dir; i <= N && i >= 1; i+=dir)
	{
		int a2;
		if(dir > 0)
			a2 = query(i-dir, i);
		else
			a2 = query(i, i-dir);
		if(lis[i-dir]+a2 > N || vis[lis[i-dir]+a2])
		{
			lis[i] = lis[i-dir]-a2;
			vis[lis[i]] = 1;
		}
		else if(lis[i-dir]-a2 < 1 || vis[lis[i-dir]-a2])
		{
			lis[i] = lis[i-dir]+a2;
			vis[lis[i]] = 1;
		}
		else
		{
			int a3;
			if(dir > 0)
				a3 = query(i-2*dir, i);
			else
				a3 = query(i, i-2*dir);
			if(a3 == abs(lis[i-dir]-lis[i-2*dir]))
			{
				if(lis[i-dir] > lis[i-2*dir])
				{
					lis[i] = lis[i-dir]-a2;
					vis[lis[i]] = 1;
				}
				else
				{
					lis[i] = lis[i-dir]+a2;
					vis[lis[i]] = 1;
				}
			}
			else
			{
				if(a3+lis[i-2*dir] == lis[i-dir]-a2)
				{
					lis[i] = a3+lis[i-2*dir];
					vis[lis[i]] = 1;
				}
				else if(lis[i-2*dir]-a3 == lis[i-dir]+a2)
				{
					lis[i] = lis[i-2*dir]-a3;
					vis[lis[i]] = 1;
				}
				else if(a3+lis[i-2*dir] == lis[i-dir]+a2)
				{
					lis[i] = a3+lis[i-2*dir];
					vis[lis[i]] = 1;
				}
				else
				{
					lis[i] = lis[i-2*dir]-a3;
					vis[lis[i]] = 1;
				}
			}
		}
	}
}

void solve(int N) {
	int pos = bs(1,N, N-1);
	vis[N] = 1;
	lis[pos] = N;
	if(pos != N)
	{
		int a1 = query(pos, pos+1);
		lis[pos+1] = N-a1;
		vis[N-a1] = 1;
	}
	
	int a1 = query(pos-1, pos);
	lis[pos-1] = N-a1;
	vis[N-a1] = 1;
	coisoetal(pos, 1, N);
	coisoetal(pos, -1, N);
	int i;
	for(i = 1; i <= N; i++)
	{
		//printf("%d %d\n", i, lis[i]);
		answer(i, lis[i]);
	}
}

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