Submission #503435

#	Time	Username	Problem	Language	Result	Execution time	Memory
503435		amunduzbaev	Xylophone (JOI18_xylophone)	C++14	100 / 100	323 ms	472 KiB

xylophone

#include "xylophone.h"
#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

//~ static int A[5000];

void solve(int n){
	vector<int> dd(n + 1);
	for(int i=2;i<=n;i++){
		dd[i] = query(i-1, i);
	}
	
	vector<int> t(n + 1);
	for(int i=3;i<=n;i++){
		t[i] = query(i-2, i);
	}
	
	vector<int> d(n + 1);
	auto go = [&](){
		for(int i=3;i<=n;i++){
			if(t[i] == dd[i-1]){
				if(d[i-1] < 0) d[i] = dd[i];
				else d[i] = -dd[i];
			} else if(t[i] == dd[i]){
				if(d[i-1] < 0) d[i] = dd[i];
				else d[i] = -dd[i];
			} else {
				if(d[i-1] < 0) d[i] = -dd[i];
				else d[i] = dd[i];
			}
		}
	};
	d[2] = dd[2], go();
	
	auto get = [&](int s){
		vector<int> a(n + 1);
		a[1] = s;
		for(int i=2;i<=n;i++){
			a[i] = a[i-1] + d[i];
		} return a;
	};
	
	for(int s=1;s<=n;s++){
		vector<int> a = get(s), cnt(n + 1);
		bool ok = 1;
		for(int i=1;i<=n;i++){
			if(a[i] < 1 || a[i] > n || cnt[a[i]]) { ok = 0; break; }
			if(a[i] == n && !cnt[1]) { ok = 0; break; }
			cnt[a[i]] = 1;
		} if(!ok) continue;
		//~ for(int i=1;i<=n;i++) cout<<a[i]<<" ";
		//~ cout<<"\n";
		for(int i=1;i<=n;i++){
			answer(i, a[i]);
		}
	}
	d[2] = -dd[2], go();
	
	for(int s=1;s<=n;s++){
		vector<int> a = get(s), cnt(n + 1);
		bool ok = 1;
		for(int i=1;i<=n;i++){
			if(a[i] < 1 || a[i] > n || cnt[a[i]]) { ok = 0; break; }
			if(a[i] == n && !cnt[1]) { ok = 0; break; }
			cnt[a[i]] = 1;
		} if(!ok) continue;
		//~ for(int i=1;i<=n;i++) cout<<a[i]<<" ";
		//~ cout<<"\n";
		for(int i=1;i<=n;i++){
			answer(i, a[i]);
		}
	}
	
	//~ assert(0);
}


/*

5
2 1 5 3 4

*/

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