제출 #444878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444878		Khizri	Xylophone (JOI18_xylophone)	C++17	100 / 100	86 ms	640 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);
			vector<int>vt{arr[i-2],arr[i-1],a};
			sort(vt.begin(),vt.end());
			if(vt[2]-vt[0]==y){
				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);
			vector<int>vt{arr[i+2],arr[i+1],a};
			sort(vt.begin(),vt.end());
			if(vt[2]-vt[0]==y){
				arr[i]=a;
				mp[a]=1;
			}
			else{
				arr[i]=b;
				mp[b]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		answer(i,arr[i]);
	}
}

컴파일 시 표준 에러 (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: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53