Submission #1097916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097916		Nurislam	Xylophone (JOI18_xylophone)	C++17	100 / 100	46 ms	600 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 id = 1;
	for(int i = 12; i >= 0; i--){
		int to = min(n, id+(1<<i));
		if(query(1, to) == n-1)continue;
		id = to;
	}
	id++;
	vector<int> df(n+1), us(n+1, 0);
	us[1] = 1;
	df[id] = 1;
	if(id < n)df[id+1] = 1 + query(id, id+1),us[df[id+1]] = 1;
	if(id > 1)df[id-1] = 1 + query(id-1, id),us[df[id-1]] = 1;
	auto r = [&]() -> void{
		for(int i = id+2; i <= n; i++){
			int dif1 = query(i-1, i);
			if(df[i-1]+dif1 > n)df[i] = df[i-1] - dif1;
			else if(df[i-1]-dif1 < 1)df[i] = df[i-1] + dif1;
			else if(us[df[i-1] - dif1])df[i] = df[i-1] + dif1;
			else if(us[df[i-1] + dif1])df[i] = df[i-1] - dif1;
			else if(df[i-2] > df[i-1]){
				int dif2 = query(i-2, i);
				if(dif2 == df[i-2] - df[i-1] + dif1)df[i] = df[i-1]-dif1;
				else df[i] = df[i-1]+dif1;
			}else{
				int dif2 = query(i-2, i);
				if(dif2 == df[i-1] - df[i-2] + dif1)df[i] = df[i-1]+dif1;
				else df[i] = df[i-1]-dif1;
			}
			us[df[i]] = 1;
		}
	};r();
	
	auto l = [&]() -> void{
		for(int i = id-2; i > 0; i--){
			int dif1 = query(i, i+1);
			if(df[i+1]+dif1 > n)df[i] = df[i+1] - dif1;
			else if(df[i+1]-dif1 < 1)df[i] = df[i+1] + dif1;
			else if(us[df[i+1] - dif1])df[i] = df[i+1] + dif1;
			else if(us[df[i+1] + dif1])df[i] = df[i+1] - dif1;
			else if(df[i+2] > df[i+1]){
				int dif2 = query(i, i+2);
				if(dif2 == df[i+2] - df[i+1] + dif1)df[i] = df[i+1]-dif1;
				else df[i] = df[i+1]+dif1;
			}else{
				int dif2 = query(i, i+2);
				if(dif2 == df[i+1] - df[i+2] + dif1)df[i] = df[i+1]+dif1;
				else df[i] = df[i+1]-dif1;
			}
			us[df[i]] = 1;
		}
	};l();
	
	
	
	
	
	
	
	
	
	
	
	
	//for(int i = 1; i <= n; i++)cout << df[i] << ' ';
	//cout << '\n';
	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: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53