Submission #1153990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153990		dosts	Xylophone (JOI18_xylophone)	C++20	100 / 100	225 ms	472 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
 
static int A[5000];

void solve(int n) {
	vi d(n+1);
	for (int i=1;i<=n-1;i++) {
		d[i] = query(i,i+1);
	}
	vi b(n+1);
	int ptr = 1;
	int dir = 1;
	for (int i = 1;i<n;) {
		int j = i+1;
		int prv = d[i];
		b[i] = dir*d[i];
		while (j<n) {
			int q = query(i,j+1);
			if (prv+d[j] != q) break;
			prv = q;
			b[j] = dir*d[j];
			j++;
		}
		i = j;
		dir=-dir;
		//i'den j'ye aynı yönde
	}
	vi p1(n+1);
	for (int s=1;s<=n;s++) {
		p1[1] = s;
		bool fl = 1;
		for (int j = 1;j<=n-1;j++) {
			p1[j+1] = p1[j]+b[j];
			if (p1[j+1] < 1 || p1[j+1] > n) {
				fl = 0;
				break;
			}
		}
		if (max_element(p1.begin()+1,p1.end()) < min_element(p1.begin()+1,p1.end())) fl = 0;
		if (fl) {
			for (int i=1;i<=n;i++) answer(i,p1[i]);
			return;
		}
	}
	for (int s=1;s<=n;s++) {
		p1[1] = s;
		bool fl = 1;
		for (int j = 1;j<=n-1;j++) {
			p1[j+1] = p1[j]-b[j];
			if (p1[j+1] < 1 || p1[j+1] > n) {
				fl = 0;
				break;
			}
		}
		if (max_element(p1.begin()+1,p1.end()) < min_element(p1.begin()+1,p1.end())) fl = 0;
		if (fl) {
			for (int i=1;i<=n;i++) answer(i,p1[i]);
			return;
		}
	}
}

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