Submission #470582

#	Time	Username	Problem	Language	Result	Execution time	Memory
470582		fatemetmhr	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	296 KiB

xylophone

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

using namespace std;

typedef long long ll;

const int maxn5 = 6e3 + 10;


int dif1[maxn5], dif2[maxn5], val[maxn5];
bool ex[maxn5];

inline bool ok(int a, int b, int c, int dif){
	int mn = min(a, min(b, c));
	int mx = max(a, max(b, c));
	return mx - mn == dif;
}

inline bool check(int ind, int n){
	val[ind] = 1;
	if(ind + 1 < n) val[ind + 1] = dif1[ind] + 1;
	if(ind - 1 >= 0) val[ind - 1] = dif1[ind - 1] + 1;
	for(int i = ind + 2; i < n; i++){
		if(ok(val[i - 2], val[i - 1], val[i - 1] + dif1[i - 1], dif2[i - 2]))
			val[i] = val[i - 1] + dif1[i - 1];
		else 
			val[i] = val[i - 1] - dif1[i - 1];
	}
	for(int i = ind - 2; i >= 0; i--){
		if(ok(val[i + 1] + dif1[i], val[i + 1], val[i + 2], dif2[i]))
			val[i] = val[i + 1] + dif1[i];
		else
			val[i] = val[i + 1] - dif1[i];
	}
	fill(ex, ex + n + 2, false);
	for(int i = 0; i < n; i++){
		if(ex[val[i]]) return false;
		ex[val[i]] = true;
		if(val[i] == n && i < ind) return false; 
	}
	return true;
}

void solve(int n){

	for(int i = 0; i < n - 1; i++) dif1[i] = query(i + 1, i + 2);
	for(int i = 0; i < n - 2; i++) dif2[i] = query(i + 1, i + 3);
	
	for(int i = 0; i < n; i++) if(check(i, n)){
		for(int j = 0; j < n; j++) 	answer(j + 1, val[j]);
		break;
	}
	return;
}

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