Submission #235331

#	Time	Username	Problem	Language	Result	Execution time	Memory
235331		amoo_safar	Xylophone (JOI18_xylophone)	C++14	100 / 100	116 ms	620 KiB

xylophone

#include <bits/stdc++.h>

#ifndef safar
#include "xylophone.h"
#endif

using namespace std;

const int N = 5e3 + 10;

#ifdef safar
	int query(int s, int t);
	void answer(int i, int ai);
#endif

int d1[N], d2[N], c[N], ps[N];
void solve(int n){
	for(int i = 1; i + 1 <= n; i++) d1[i] = query(i, i + 1);
	for(int i = 1; i + 2 <= n; i++) d2[i] = query(i, i + 2);
	c[1] = 1;
	for(int i = 2; i + 1 <= n; i++) c[i] = (d1[i - 1] + d1[i] == d2[i - 1] ? 1 : -1) * c[i - 1];
	ps[1] = 0;
	for(int i = 2; i <= n; i++) ps[i] = ps[i - 1] + c[i - 1] * d1[i - 1];
	int mn = *min_element(ps + 1, ps + 1 + n);
	for(int i = 1; i <= n; i++) ps[i] += 1 - mn;
	if(min_element(ps + 1, ps + 1 + n)-ps > max_element(ps + 1, ps + 1 + n)-ps){
		for(int i = 1; i <= n; i++) ps[i] = n + 1 - ps[i];
	}
	for(int i = 1; i <= n; i++) answer(i, ps[i]);
	return ;
}

#ifdef safar
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	return 0;
}
#endif

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