Submission #1217671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217671		Muhammet	Xylophone (JOI18_xylophone)	C++20	47 / 100	24 ms	432 KiB

xylophone

#include "bits/stdc++.h"
#include "xylophone.h"
// #include "grader.cpp"

using namespace std;

void solve(int n) {

	int cnt = 1;
	int k = (query (1, n));

	int l1 = 1, r1 = n, l;
	while(l1 <= r1) {
		int md = (l1 + r1) / 2;
		if(query(md, n) == k) {
			l1 = md+1;
		}
		else {
			r1 = md-1;
			l = md-1;
		}
	}

	vector <int> ans1(n+1, 0);
	ans1[l] = 1;
	if(l > 1) ans1[l-1] = ans1[l] + query(l-1, l), cnt++;

	for(int i = l-2; i > 0; i--) {
		int x = ans1[i+1], y = ans1[i+2];
		k = query(i, i+2);
		cnt += 2;
		int k1 = query(i, i+1);
		if(x > y) {
			if(k == (x + k1 - y)) ans1[i] = x + k1;
			else ans1[i] = x - k1;
		}
		else {
			if(k == (y - (x - k1))) ans1[i] = x - k1;
			else ans1[i] = x + k1;
		}
	}

	cnt++;
	ans1[l+1] = ans1[l] + query(l, l+1);

	for(int i = l+2; i <= n; i++) {
		int x = ans1[i-1], y = ans1[i-2];
		cnt += 2;
		k = query(i-2, i);
		int k1 = query(i-1, i);
		if(x > y) {
			if(k == (x + k1 - y)) ans1[i] = x + k1;
			else ans1[i] = x - k1;
		}
		else {
			if(k == (y - (x - k1))) ans1[i] = x - k1;
			else ans1[i] = x + k1;
		}
	}

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

}

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