Submission #598492

#	Time	Username	Problem	Language	Result	Execution time	Memory
598492		GioChkhaidze	Xylophone (JOI18_xylophone)	C++14	47 / 100	98 ms	332 KiB

xylophone

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

using namespace std;

int n, a[5005];

void slv(int x) {
	if (x == 1) return ;
	vector < int > v2, v3;
	for (int i = x; i >= 1; --i) {
		if (i - 1 >= 1) v2.pb(query(i - 1, i));
		if (i - 2 >= 1) v3.pb(query(i - 2, i));
	}
	a[x - 1] = 1 + v2[0];
	int i2 = 1, i3 = 0;
	for (int i = x - 2; i >= 1; --i) {
		int ps1 = a[i + 1] + v2[i2];
		int ps2 = a[i + 1] - v2[i2];
		int mx = max(a[i + 1], a[i + 2]);
		int mn = min(a[i + 1], a[i + 2]);
		if (ps1 > n) a[i] = ps2;
			else
		if (ps2 < 1) a[i] = ps1;
			else
		if (max(mx, ps1) - min(mn, ps1) == v3[i3]) a[i] = ps1;
			else
		if (max(mx, ps2) - min(mn, ps2) == v3[i3]) a[i] = ps2;
		++i2, ++i3;
	}
}

void srv(int x) {
	vector < int > v2, v3;
	for (int i = x; i <= n; ++i) {
		if (i + 1 <= n) v2.pb(query(i, i + 1));
		if (i + 2 <= n) v3.pb(query(i, i + 2));
	}
	a[x + 1] = 1 + v2[0];
	int i2 = 1, i3 = 0;
	for (int i = x + 2; i <= n; ++i) {
		int ps1 = a[i - 1] + v2[i2];
		int ps2 = a[i - 1] - v2[i2];
		int mx = max(a[i - 1], a[i - 2]);
		int mn = min(a[i - 1], a[i - 2]);
		if (ps1 > n) a[i] = ps2;
			else
		if (ps2 < 1) a[i] = ps1;
			else
		if (max(mx, ps1) - min(mn, ps1) == v3[i3]) a[i] = ps1;
			else
		if (max(mx, ps2) - min(mn, ps2) == v3[i3]) a[i] = ps2;
		++i2, ++i3;
	}
}

void solve(int N) {	
	n = N;
	int l = 1, r = n - 1, mid, res = -1;
	while (l <= r) {
		int mid = ((l + r) >> 1);
		if (query(mid, n) == n - 1) {
			l = mid + 1, res = mid;
		}
			else {
			r = mid - 1;		
		}
	}
	
	a[res] = 1, slv(res), srv(res);
	for(int i = 1; i <= n; i++) {
		answer(i, a[i]);
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:60:24: warning: unused variable 'mid' [-Wunused-variable]
   60 |  int l = 1, r = n - 1, mid, res = -1;
      |                        ^~~

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