Submission #1136994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136994		PlayVoltz	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	420 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;
			got[ans[i]]=1;
		}
		else if (ans[i-1]+d>n||got[ans[i-1]+d]){
			ans[i]=ans[i-1]-d;
			got[ans[i]]=1;
		}
		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;
					got[ans[i]]=1;
				}
				else{
					ans[i]=ans[i-1]+d;
					got[ans[i]]=1;
				}
			}
			else{
				if (temp==ans[i-2]-ans[i-1]+d){
					ans[i]=ans[i-1]+d;
					got[ans[i]]=1;
				}
				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;
			got[ans[i]]=1;
		}
		else if (ans[i+1]+d>n||got[ans[i+1]+d]){
			ans[i]=ans[i+1]-d;
			got[ans[i]]=1;
		}
		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;
					got[ans[i]]=1;
				}
				else{
					ans[i]=ans[i+1]+d;
					got[ans[i]]=1;
				}
			}
			else{
				if (temp==ans[i+2]-ans[i+1]+d){
					ans[i]=ans[i+1]+d;
					got[ans[i]]=1;
				}
				else{
					ans[i]=ans[i+1]-d;
					got[ans[i]]=1;
				}
			}
		}
	}
	for (int i=1; i<=n; ++i)answer(i, ans[i]);
}

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