Submission #764518

#	Time	Username	Problem	Language	Result	Execution time	Memory
764518		sysia	Xylophone (JOI18_xylophone)	C++17	100 / 100	90 ms	432 KiB

xylophone

//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "xylophone.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

void solve(int n){
	vector<int>a(n+1);
	for (int i = 1; i<n; i++) a[i] = query(i, i+1);
	//a[i] = abs(p[i] - p[i+1])
	vector<int>dir(n+1);
	for (int i = 1; i+2 <= n; i++){
		int x = query(i, i+2);
		if (a[i] + a[i+1] == x){
			dir[i+1] = dir[i];
		} else {
			dir[i+1] = dir[i]^1;
		}
	}
	for (int rep = 0; rep < 2; rep++){
		vector<int>p(n+1);
		int mn = 0;
		for (int i = 1; i<n; i++){
			if (dir[i]) p[i+1] = p[i] + a[i];
			else p[i+1] = p[i] - a[i];
			mn = min(mn, p[i+1]);
		}
		for (int i = 1; i<=n; i++) {
			p[i] += (1-mn);
		}
		debug(p);
		bool was = 0;
		bool ok = 1;
		for (int i = 1; i<=n; i++){
			if (p[i] < 1 || p[i] > n) {
				ok = 0;
				break;
			}
			if (p[i] == 1) was = 1;
			if (p[i] == n){
				if (!was) ok = 0;
			}
		}
		if (ok){
			debug(p);
			for (int i = 1; i<=n; i++) answer(i, p[i]);
			return;
		}
		for (int i = 1; i<n; i++) dir[i]^=1;
	}
	assert(false);
}

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