Submission #1085322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085322		4QT0R	Xylophone (JOI18_xylophone)	C++17	100 / 100	78 ms	724 KiB

xylophone

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

void solve(int n){
	vector<int> zap(n+1);
	for (int i = 1; i<n; i++){
		zap[i]=query(i,i+1);
	}
	vector<int> ciag(n+1);
	ciag[1]=zap[1];
	for (int i = 2; i<n; i++){
		int q=query(i-1,i+1);
		if (zap[i-1]==q || zap[i]==q)ciag[i]=ciag[i-1]+zap[i]*(ciag[i-2]<ciag[i-1]?-1:1);
		else ciag[i]=ciag[i-1]+zap[i]*(ciag[i-2]<ciag[i-1]?1:-1);
	}
	int mn=0,mn_ind=0,mx=0,mx_ind=0;
	for (int i = 1; i<n; i++){
		if (mn>ciag[i]){
			mn=ciag[i];
			mn_ind=i;
		}
		if (mx<ciag[i]){
			mx=ciag[i];
			mx_ind=i;
		}
	}
	if (mn_ind>mx_ind){
		for (int i = 0; i<n; i++)ciag[i]=-ciag[i];
		mn=-mn;
		mx=-mx;
		swap(mn,mx);
	}
	for (int i = 0; i<n; i++)answer(i+1,ciag[i]-mn+1);
}

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