Submission #1097902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097902		Nurislam	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	344 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
//static int A[5000];

void solve(int n) {
	int mx = 0, id = 1;
	for(int i = 2; i <= n; i++){
		if(chmax(mx, query(1, i)))id = i;
	}
	vector<int> df(n+1), us(n+1, 0);
	int last = 0;
	us[1] = id;
	df[id] = 1;
	for(int i = id+1; i <= n; i++){
		int dif = query(i-1, i), cur = 0;
		if(df[i-1]+dif > n)cur = df[i-1] - dif;
		else if(df[i-1]-dif < 1)cur = df[i-1] + dif;
		else if(us[df[i-1] - dif])cur = df[i+1] + dif;
		else if(us[df[i-1] + dif])cur = df[i-1] - dif;
		else{
			int dif1 = query(id, i);
			if(chmax(last, dif1))cur = dif1 + 1;
			else cur = df[i-1] - dif;
		}
		us[cur] = i;
		df[i] = cur;
		chmax(last, df[i] - 1);
	}
	last = 0;
	for(int i = id-1; i > 0; i--){
		int dif = query(i, i+1), cur = 0;
		if(df[i+1]+dif > n)cur = df[i+1] - dif;
		else if(df[i+1]-dif < 1)cur = df[i+1] + dif;
		else if(us[df[i+1] - dif])cur = df[i+1] + dif;
		else if(us[df[i+1] + dif])cur = df[i-1] - dif;
		else{
			int dif1 = query(i, id);
			if(chmax(last, dif1))cur = dif1 + 1;
			else cur = df[i+1] - dif;
		}
		us[cur] = i;
		df[i] = cur;
		chmax(last, df[i] - 1);
	}
	//for(int i = 1; i <= n; i++)cout << df[i] << ' ';
	//cout << '\n';
	bool ch = 0;
	for(int i = 1; i <= id; i++)if(df[i] == n)ch = 1;
	if(ch)
		for(int i = 1; i <= n; i++)
			df[i] = n - df[i] + 1;
	//cout << ch << '\n';
	for(int i = 1; i <= n; i++){
		answer(i, df[i]);
	}
}

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