Submission #470587

#	Time	Username	Problem	Language	Result	Execution time	Memory
470587		fatemetmhr	Xylophone (JOI18_xylophone)	C++17	100 / 100	269 ms	448 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 int query(int l, int r){
	cout << "asked " << l << ' ' << r << endl;
	int a; cin >> a;
	return a;
}

inline void answer(int i, int a){
	cout << "answering to " << i << ' ' << a << endl;
	return;
}
*/

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(val[i] < 1 || val[i] > n || 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);
	
	bool done = false;
	for(int i = 0; i < n; i++) if(check(i, n)){
		for(int j = 0; j < n; j++) 	answer(j + 1, val[j]);
		done = true;
		break;
	}
	return;
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:63:7: warning: variable 'done' set but not used [-Wunused-but-set-variable]
   63 |  bool done = false;
      |       ^~~~

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