Submission #66557

#	Time	Username	Problem	Language	Result	Execution time	Memory
66557		zadrga	Xylophone (JOI18_xylophone)	C++14	100 / 100	81 ms	724 KiB

xylophone

/*
Idea:
- http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2018/2018-open-xylophone-sol-en.pdf
*/

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (int) (2 * 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 5111

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

int ret[maxn];
bool used[maxn];

void solve(int N){
	int l = 2, d = N, max_ind = -1;
	while(l <= d){
		int mid = (l + d) / 2;
		int val = query(1, mid);
		if(val == N - 1){
			max_ind = mid;
			d = mid - 1;
		}
		else
			l = mid + 1; 
	}

	ret[max_ind] = N;
	used[N] = 1;

	if(max_ind + 1 <= N){
		int cur = query(max_ind, max_ind + 1);
		ret[max_ind + 1] = N - cur;
		used[N - cur] = 1;
	}

	if(max_ind - 1 >= 1){
		int cur = query(max_ind - 1, max_ind);
		ret[max_ind - 1] = N - cur;
		used[N - cur] = 1;
	}

	for(int i = max_ind + 2; i <= N; i++){
		int diff = query(i - 1, i);
		int opt1 = ret[i - 1] + diff;
		int opt2 = ret[i - 1] - diff;

		if(opt1 < 1 || opt1 > N || used[opt1]){
			ret[i] = opt2;
			used[ret[i]] = 1;
			continue;
		}

		if(opt2 < 1 || opt2 > N || used[opt2]){
			ret[i] = opt1;
			used[ret[i]] = 1;
			continue;
		}

		int updown = query(i - 2, i);
		if(max(ret[i - 2], max(ret[i - 1], opt1)) - min(ret[i - 2], min(ret[i - 1], opt1)) == updown){
			ret[i] = opt1;
		}
		else
			ret[i] = opt2;

		used[ret[i]] = 1;
	}

	for(int i = max_ind - 2; i >= 1; i--){
		int diff = query(i, i + 1);
		int opt1 = ret[i + 1] + diff;
		int opt2 = ret[i + 1] - diff;

		if(opt1 < 1 || opt1 > N || used[opt1]){
			ret[i] = opt2;
			used[ret[i]] = 1;
			continue;
		}

		if(opt2 < 1 || opt2 > N || used[opt2]){
			ret[i] = opt1;
			used[ret[i]] = 1;
			continue;
		}

		int updown = query(i, i + 2);
		if(max(ret[i + 2], max(ret[i + 1], opt1)) - min(ret[i + 2], min(ret[i + 1], opt1)) == updown){
			ret[i] = opt1;
		}
		else
			ret[i] = opt2;

		used[ret[i]] = 1;
	}

	for(int i = 1; i <= N; i++){
		answer(i, ret[i]);
	}
}

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