Submission #102128

#	Time	Username	Problem	Language	Result	Execution time	Memory
102128		SpeedOfMagic	Xylophone (JOI18_xylophone)	C++17	100 / 100	100 ms	504 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

static int A[5000];
char has[5000];
void ans(int ind, int val) {
	has[val] = 1;
	A[ind] = val;
	answer(ind + 1, val);
}

int n;
void sset(int i, int pr, int ppr) {
	int p = query(min(i, pr) + 1, max(i, pr) + 1);
	if (A[pr] - p > 0 && A[pr] + p <= n) {
		int d = query(min(i, ppr) + 1, max(i, ppr) + 1);
		if (max(max(A[pr] + p, A[pr]), A[ppr]) - min(min(A[pr] + p, A[pr]), A[ppr]) == d)
			A[i] = A[pr] + p;
		else
			A[i] = A[pr] - p;
	} else {
		if (A[pr] - p <= 0)
			A[i] = A[pr] + p;
		else
			A[i] = A[pr] - p;
	}
	ans(i, A[i]);
}


void solve(int N) {
	n = N;
	memset(has, 0, sizeof has);
	int l = 1, r = N;
	while (l < r) {
		int mid = (l + r) >> 1;
		int p = query(1, mid);
		if (p == N - 1)
			r = mid;
		else
			l = mid + 1;
	}
	
	l--;
	ans(l, N);
	
	if (l <= N / 2) {
		for (int i = l - 1; i >= 0; i--) 
			sset(i, i + 1, i + 2);
		
		for (int i = l + 1; i < N - 20; i++)
			sset(i, i - 1, i - 2);
		l = max(N - 20, l + 1);
		int siz = N - l + 1;
		
		int vals[N];
		for (int i = l; i < N; i++)
			vals[i] = query(i, i + 1);
		for (int mask = 0; mask < (1 << siz); mask++) {
			int cval = A[l - 1];
			
			for (int j = l; j < N; j++) {
				if (mask & (1 << (j - l)))
					cval -= vals[j];
				else
					cval += vals[j];
				if (has[cval] || cval <= 0 || cval > N) {
					for (int k = j - 1; k >= l; k--) 
						has[A[k]] = 0;
					goto nxt;
				} else {
					has[cval] = 1;
					A[j] = cval;
				}
			}
			
			for (int j = l; j < N; j++)
				ans(j, A[j]);
			return;
			nxt:;
		}
			
	} else {
		for (int i = l + 1; i < N; i++) 
			sset(i, i - 1, i - 2);
		
		for (int i = l - 1; i >= 20; i--) 
			sset(i, i + 1, i + 2);
		
		l = min(19, l - 1);
		int siz = l + 1;
		
		int vals[N];
		for (int i = 0; i <= l; i++)
			vals[i] = query(i + 1, i + 2);
		for (int mask = 0; mask < (1 << siz); mask++) {
			int cval = A[l + 1];
			for (int j = l; j >= 0; j--) {
				if (mask & (1 << (l - j)))
					cval -= vals[j];
				else
					cval += vals[j];
				if (has[cval] || cval > N || cval <= 0) {
					for (int k = j + 1; k <= l; k++) 
						has[A[k]] = 0;
					goto nxt2;
				} else {
					has[cval] = 1;
					A[j] = cval;
				}
			}
			
			for (int j = 0; j <= l; j++)
				ans(j, A[j]);
			return;
			nxt2:;
		}
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:94:7: warning: argument 1 range [18446744065119617024, 18446744073709551608] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
   int vals[N];
       ^~~~
xylophone.cpp:94:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'

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