Submission #1156749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156749		Hamed_Ghaffari	Xylophone (JOI18_xylophone)	C++20	100 / 100	26 ms	476 KiB

xylophone

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

const int MXN = 5003;

int val2[MXN], val3[MXN], dif[MXN];

void solve(int n) {
	for(int i=2; i<=n; i++) {
		dif[i] = val2[i] = query(i-1, i);
		if(i>2) val3[i] = query(i-2, i);
	}
	for(int i=3; i<=n; i++)
		if((val2[i-1]+val2[i]==val3[i])==(dif[i-1]<0))
			dif[i] *= -1;
	dif[1] = n*(n+1)/2;
	for(int i=2; i<=n; i++) dif[1] -= dif[i]*(n+1-i);
	dif[1] /= n;
	for(int i=2; i<=n; i++) dif[i] += dif[i-1];
	int pos1=-1, posn=-1;
	for(int i=1; i<=n; i++)
		if(dif[i]==1) pos1=i;
		else if(dif[i]==n) posn=i;
	if(pos1>posn) {
		for(int i=1; i<=n; i++) dif[i] = n+1-dif[i];
	}
	for(int i=1; i<=n; i++) {
		answer(i, dif[i]);
	}
}

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