Submission #1137001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137001		PlayVoltz	Xylophone (JOI18_xylophone)	C++20	100 / 100	17 ms	436 KiB

xylophone

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

static int A[5000];

void solve(int n){
	vector<int> ans(n+1);
	vector<bool> got(n+1, 0);
	int low=0, high=n+1;
	while (low+1<high){
		int mid=(low+high)/2;
		if (query(mid, n)==n-1)low=mid;
		else high=mid;
	}
	got[1]=1;
	ans[low]=1;
	if (low+1<=n)ans[low+1]=1+query(low, low+1), got[ans[low+1]]=1;
	for (int i=low+2; i<=n; ++i){
		int d=query(i-1, i);
		if (ans[i-1]-d<=0||got[ans[i-1]-d])ans[i]=ans[i-1]+d;
		else if (ans[i-1]+d>n||got[ans[i-1]+d])ans[i]=ans[i-1]-d;
		else{
			int temp=query(i-2, i);
			if (ans[i-2]>ans[i-1]){
				if (temp==ans[i-2]-ans[i-1]+d)ans[i]=ans[i-1]-d;
				else ans[i]=ans[i-1]+d;
			}
			else{
				if (temp==ans[i-1]-ans[i-2]+d)ans[i]=ans[i-1]+d;
				else ans[i]=ans[i-1]-d;
			}
		}
		got[ans[i]]=1;
	}
	if (low>1)ans[low-1]=1+query(low-1, low), got[ans[low-1]]=1;
	for (int i=low-2; i>=1; --i){
		int d=query(i, i+1);
		if (ans[i+1]-d<=0||got[ans[i+1]-d])ans[i]=ans[i+1]+d;
		else if (ans[i+1]+d>n||got[ans[i+1]+d])ans[i]=ans[i+1]-d;
		else{
			int temp=query(i, i+2);
			if (ans[i+2]>ans[i+1]){
				if (temp==ans[i+2]-ans[i+1]+d)ans[i]=ans[i+1]-d;
				else ans[i]=ans[i+1]+d;
			}
			else{
				if (temp==ans[i+1]-ans[i+2]+d)ans[i]=ans[i+1]+d;
				else ans[i]=ans[i+1]-d;
			}
		}
		got[ans[i]]=1;
	}
	for (int i=1; i<=n; ++i)answer(i, ans[i]);
}

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