Submission #169762

#	Time	Username	Problem	Language	Result	Execution time	Memory
169762		Mounir	Xylophone (JOI18_xylophone)	C++14	0 / 100	2 ms	376 KiB

xylophone

#include <bits/stdc++.h>
using namespace std;
 
void answer(int i, int j);
int query(int i, int j);
 
void solve(int N){
	int nVals = N;
	vector<int> vals(nVals), diffVoisin(nVals), signe(nVals);
	for (int& val : vals)
		val = 0;
	
	for (int iVal = 0; iVal < nVals - 1; ++iVal)
		diffVoisin[iVal] = query(iVal + 1, iVal + 2);
		
	for (int signe0 = -1; signe0 <= 1; signe0 += 2){
		signe[0] = signe0;
		for (int iVal = 1; iVal < nVals - 1; ++iVal){
			if (query(iVal + 1, min(nVals, iVal + 3)) == diffVoisin[iVal] + diffVoisin[iVal + 1])
				signe[iVal] = signe[iVal - 1];
			else
				signe[iVal] = -signe[iVal - 1];
		}
		//On vérifie que ca fait une permutation, càd que tout soit distinct
		vals[0] = 1;
		set<int> verif;
		for (int iVal = 0; iVal < nVals - 1; ++iVal){
			vals[iVal + 1] = vals[iVal] + signe[iVal] * diffVoisin[iVal];
			verif.insert(vals[iVal]);
		}
		
	//	for (int& i : vals)
		//	cout << i << " ";
		//cout << endl;
		verif.insert(vals[nVals - 1]);
	
		if ((int)verif.size() == nVals && vals[0] < vals[nVals - 1]){
			int delta = 1 - *verif.begin();
			for (int iVal = 0; iVal < nVals; ++iVal)
				answer(iVal + 1, vals[iVal] + delta);
		}
	}
}

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