Submission #67352

#	Time	Username	Problem	Language	Result	Execution time	Memory
67352		Kmcode	Xylophone (JOI18_xylophone)	C++14	100 / 100	110 ms	1288 KiB

xylophone

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_set>
#include<unordered_map>

using namespace std;


//void solve(int N);
//int query(int s, int t);
//void answer(int i, int a);

#include "xylophone.h"


map<pair<int, int>, int> mp;
int ask(int a, int b){
	if (mp.count(make_pair(a, b))){
		return mp[make_pair(a, b)];
	}
	mp[make_pair(a, b)] = query(a, b);
	return mp[make_pair(a, b)];
}
int ans[5002];

set<int> usesd;
void solve(int N) {
	int mint = 1;
	int maxt = N;
	while (mint + 1 < maxt){
		int mid = (mint + maxt) >> 1;
		if (ask(1, mid) >= N-1){
			maxt = mid;
		}
		else{
			mint = mid + 1;
		}
	}
	if (ask(1, mint) >= N-1){
		maxt=mint;
	}
	else{
		mint = maxt;
	}
	int pos = mint;
	ans[pos] = N;
	for (int i = pos + 1; i <= N; i++){
		int dif = ask(i - 1, i);
		int n1 = ans[i-1] - dif;
		int n2 = ans[i - 1] + dif;
		if (n1<1||usesd.count(n1)){
			usesd.insert(n2);
			ans[i] = n2;
			continue;
		}
		if (n2 > N || usesd.count(n2)){
			usesd.insert(n1);
			ans[i] = n1;
			continue;
		}
		int F = ask(i-2, i);
		int mint = min(min(ans[i - 1], n1), ans[i - 2]);
		int maxt = max(max(ans[i - 1], n1), ans[i - 2]);
		if (maxt - mint == F){
			usesd.insert(n1);
			ans[i] = n1;
			continue;
		}
		usesd.insert(n2);
		ans[i] = n2;
	}for (int i = pos - 1; i >=1 ; i--){
		int dif = ask(i, i+1);
		int n1 = ans[i + 1] - dif;
		int n2 = ans[i + 1] + dif;
		if (n1<1 || usesd.count(n1)){
			usesd.insert(n2);
			ans[i] = n2;
			continue;
		}
		if (n2 > N || usesd.count(n2)){
			usesd.insert(n1);
			ans[i] = n1;
			continue;
		}
		int F = ask(i, i+2);
		int mint = min(min(ans[i + 1], n1), ans[i + 2]);
		int maxt = max(max(ans[i + 1], n1), ans[i + 2]);
		if (maxt - mint == F){
			usesd.insert(n1);
			ans[i] = n1;
			continue;
		}
		usesd.insert(n2);
		ans[i] = n2;
	}
	for (int i = 1; i <= N; i++) {
		answer(i, ans[i]);
	}

}

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