Submission #127613

#	Time	Username	Problem	Language	Result	Execution time	Memory
127613		Markomafko972	Xylophone (JOI18_xylophone)	C++14	100 / 100	121 ms	568 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int n) {
	int t[5002];
	memset(t, 0, sizeof t);
	int q[5][5002];
	memset(q, 0, sizeof q);
	q[0][2] = query(1, 2);
	t[2] = q[0][2];
	
	int e = min(t[1], t[2]);
	for (int i = 3; i <= n; i ++) {
		q[0][i] = query(i-1, i);
		q[1][i] = query(i-2, i);
		if (t[i-2] < t[i-1]) {
			if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] - q[0][i];
			else t[i] = t[i-1] + q[0][i];
		}
		else {
			if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] + q[0][i];
			else t[i] = t[i-1] - q[0][i];
		}
		
		e = min(e, t[i]);
	}
	
	int bio[5002];
	memset(bio, 0, sizeof bio);
	int p = 0;
	int ne = 0;
	for (int i = 1; i <= n; i ++) {
		t[i] -= e-1;
		if (t[i] >= 1 && t[i] <= n) bio[t[i]] ++;
		if (t[i] == 1) p = 1;
		
		if (t[i] == n && p == 0) {
			ne = 1;
		}
	}
	
	int da = 1;
	for (int i = 1; i <= n; i ++) {
		if (bio[i] != 1) {
			da = 0;
			break;
		}
	}
	
	if (da == 1 && ne == 0) {
		for (int i = 1; i <= n; i ++) {
			answer(i, t[i]);
		}
		
		return;
	}
	
	memset(t, 0, sizeof t);
	t[2] = -q[0][2];
	
	e = min(t[1], t[2]);
	for (int i = 3; i <= n; i ++) {
		if (t[i-2] < t[i-1]) {
			if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] - q[0][i];
			else t[i] = t[i-1] + q[0][i];
		}
		else {
			if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] + q[0][i];
			else t[i] = t[i-1] - q[0][i];
		}
		
		e = min(e, t[i]);
	}
	
	memset(bio, 0, sizeof bio);
	p = 0;
	ne = 0;
	for (int i = 1; i <= n; i ++) {
		t[i] -= e-1;
		if (t[i] >= 1 && t[i] <= n) bio[t[i]] ++;
		if (t[i] == 1) p = 1;
		
		if (t[i] == n && p == 0) {
			ne = 1;
		}
	}
	
	da = 1;
	for (int i = 1; i <= n; i ++) {
		if (bio[i] != 1) {
			da = 0;
			break;
		}
	}
	
	if (da == 1 && ne == 0) {
		for (int i = 1; i <= n; i ++) {
			answer(i, t[i]);
		}
		
		return;
	}
	assert(0);
}

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