Submission #930085

#	Time	Username	Problem	Language	Result	Execution time	Memory
930085		ByeWorld	Xylophone (JOI18_xylophone)	C++14	100 / 100	48 ms	1704 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
//#define int long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int INF = 1e9+10;
const int MAXN = 2e3+10;
int A[5010], tag[5010];

int n;

void solve(int N) {
	n = N;
	int val = n-1, l = 1, r = n, las = 1;
	while(l <= r){
		int te = query(md, n);
		if(te==n-1){
			las = md; l = md+1; 
		} else r = md-1;	
	}
	// las -> 1
	A[las] = 1;

	for(int i=las-1; i>=1; i--){ // ke kiri
		if(i==las-1){
			int te = query(las-1, las);
			A[las-1] = te+1;
			tag[A[i]] = 1;
			continue;
		}

		// ngerjain A[i]
		int dif = query(i, i+1); // consider A[i+1]-dif / A[i]+dif
		if(tag[A[i+1]-dif]){
			A[i] = A[i+1]+dif; 
			tag[A[i]] = 1;
			continue;
		} 
		if(tag[A[i+1]+dif]){
			A[i] = A[i+1]-dif; 
			tag[A[i]] = 1;
			continue;
		} 

		if(A[i+1] < A[i+2]){ // lebih tinggi, cek yg -dif
			int cek = A[i+2] - (A[i+1]-dif);
			if(query(i, i+2) == cek) A[i] = A[i+1]-dif;
			else A[i] = A[i+1]+dif;
		} else { // lebih rendah
			int cek = (A[i+1]+dif) - A[i+2];
			if(query(i, i+2) == cek) A[i] = A[i+1]+dif;
			else A[i] = A[i+1]-dif;
		}
		tag[A[i]] = 1;
	}
	for(int i=las+1; i<=n; i++){
		if(i==las+1){
			int te = query(las, las+1);
			A[las+1] = te+1;
			tag[A[i]] = 1;
			continue;
		}

		// ngerjain A[i]
		int dif = query(i-1, i); // consider A[i-1]-dif / A[i-1]+dif
		if(tag[A[i-1]-dif]){
			A[i] = A[i-1]+dif; 
			tag[A[i]] = 1;
			continue;
		}
		if(tag[A[i-1]+dif]){
			A[i] = A[i-1]-dif; 
			tag[A[i]] = 1;
			continue;
		}

		if(A[i-2] < A[i-1]){ // lebih tinggi, cek yg +dif
			int cek = (A[i-1]+dif) - A[i-2];
			if(query(i-2, i) == cek) A[i] = A[i-1]+dif;
			else A[i] = A[i-1]-dif;
		} else { // lebih rendah
			int cek = A[i-2] - (A[i-1]-dif);
			if(query(i-2, i) == cek) A[i] = A[i-1]-dif;
			else A[i] = A[i-1]+dif;
		}
		tag[A[i]] = 1;
	}

	//for(int i = 1; i <= n; i++) cout << A[i] << " \n"[i==n];
	for(int i = 1; i <= n; i++) {
		answer(i, A[i]);
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:21:6: warning: unused variable 'val' [-Wunused-variable]
   21 |  int val = n-1, l = 1, r = n, las = 1;
      |      ^~~

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