Submission #198577

#	Time	Username	Problem	Language	Result	Execution time	Memory
198577		algorithm16	Xylophone (JOI18_xylophone)	C++14	100 / 100	142 ms	512 KiB

xylophone

#include "xylophone.h"
#include<iostream>
#include<algorithm>
using namespace std;
int arr[5005],d[5005];
void solve(int N) {
	int x=0,ind1=0,ind2=0,mini=0,maxi=0;
	arr[0]=x;
	arr[1]=x+query(1,2);
	if(arr[1]>maxi) {
		maxi=arr[1];
		ind2=1;
	}
	if(arr[1]<mini) {
		mini=arr[1];
		ind1=1;
	}
	d[1]=arr[1];
	for(int i=2;i<N;i++) {
		int d1=query(i,i+1);
		if(query(i-1,i+1)==d[i-1]+d1) {
			if(arr[i-1]>arr[i-2]) arr[i]=arr[i-1]+d1;
			else arr[i]=arr[i-1]-d1;
		}
		else {
			if(arr[i-1]>arr[i-2]) arr[i]=arr[i-1]-d1;
			else arr[i]=arr[i-1]+d1;
		}
		d[i]=d1;
		if(arr[i]>maxi) {
			maxi=arr[i];
			ind2=i;
		}
		if(arr[i]<mini) {
			mini=arr[i];
			ind1=i;
		}
	}
	/*for(int i=0;i<N;i++) {
		cout << arr[i] << " " << d[i] << "\n";
	}*/
	if(ind1>ind2 or maxi+1-mini>N) {
		swap(mini,maxi);
		mini=-mini;
		maxi=-maxi;
		for(int i=1;i<=N;i++) {
			answer(i,-arr[i-1]+1-mini);
			//cout << -arr[i-1]+1-mini << " ";
		}
		//cout << "\n";
	}
	else {
		for(int i=1;i<=N;i++) {
			answer(i,arr[i-1]+1-mini);
			//cout << arr[i-1]+1-mini << " ";
		}
		//cout << "\n";
	}
}

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