Submission #444864

#	Time	Username	Problem	Language	Result	Execution time	Memory
444864		Khizri	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	200 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int arr[5005];
int dp[5005];
map<int,bool>mp;
void solve(int n) {
	int l=1,r=n,k;
	while(l<=r){
		int m=(l+r)/2;
		if(query(m,n)==n-1){
			l=m+1;
			k=m;
		}
		else{
			r=m-1;
		}
	}
	arr[k]=1;
	mp[1]=1;
	for(int i=k+1;i<=n;i++){
		int x=query(i-1,i);
		dp[i-1]=x;
		int a=arr[i-1]+x;
		int b=arr[i-1]-x;
		if(a<=0||a>n||mp[a]){
			arr[i]=b;
			mp[b]=1;
		}
		else if(b<=0||b>n||mp[b]){
			arr[i]=a;
			mp[a]=1;
		}
		else{
			int y=query(i-2,i);
			if(dp[i-2]>y){
				arr[i]=a;
				mp[a]=1;
			}
			else if(dp[i-2]<y){
				arr[i]=b;
				mp[b]=1;
			}
			else{
				if(min(arr[i-2],arr[i-1])<=a&&a<=max(arr[i-2],arr[i-1])){
					arr[i]=a;
					mp[a]=1;
				}
				else{
					arr[i]=b;
					mp[b]=1;
				}
			}
		}
	}
	for(int i=k-1;i>=1;i--){
		int x=query(i,i+1);
		dp[i+1]=x;
		int a=arr[i+1]+x;
		int b=arr[i+1]-x;
		if(a<=0||a>n||mp[a]){
			arr[i]=b;
			mp[b]=1;
		}
		else if(b<=0||b>n||mp[b]){
			arr[i]=a;
			mp[a]=1;
		}
		else{
			int y=query(i,i+2);
			if(dp[i+2]>y){
				arr[i]=a;
				mp[a]=1;
			}
			else if(dp[i+2]<y){
				arr[i]=b;
				mp[b]=1;
			}
			else{
				if(min(arr[i+2],arr[i+1])<=a&&a<=max(arr[i+2],arr[i+1])){
					arr[i]=a;
					mp[a]=1;
				}
				else{
					arr[i]=b;
					mp[b]=1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		answer(i,arr[i]);
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:8:14: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
    8 |  int l=1,r=n,k;
      |              ^

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