Submission #496610

#	Time	Username	Problem	Language	Result	Execution time	Memory
496610		ignaciocanta	Xylophone (JOI18_xylophone)	C++14	0 / 100	3068 ms	200 KiB

xylophone

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

static int A[5000];

void solve(int n) {
	int low = 1, high = n;
	while(high - low > 1){
		int mid = low + (high - low) / 2;
		if(query(1, mid) == n - 1) high = mid;
		else low = mid;
	}
	int posN = high;
	low = 1, high = n;
	while(high - low > 1){
		int mid = low + (high - low) / 2;
		if(query(mid, n) == n - 1) low = mid;
		else high = mid;
	}
	vector<set<int>> cands(n+1);
	vector<int> r(n);
	for(int i = 1; i < n; ++i){
		r[i] = query(i, i+1);
	}
	vector<bool> seen(n+1, 0), use(n+1, 0);
	cands[posN].insert(n);
	cands[low].insert(1);
	int tot = 0;
	while(tot < n){
		for(int i = 1; i <= n; ++i){
			if(int(cands[i].size()) == 1){
				int todo = *cands[i].begin();
				use[i] = 1;
				//cout << "En " << i << " va " << todo << "\n";
				answer(i, *cands[i].begin());
				seen[todo] = 1;
				++tot;
			}
			for(auto& todo : cands[i]){
				if(i + 1 <= n && !use[i+1]){
					int r1 = r[i];
					if(todo + r1 <= n && !seen[todo+r1]){
						cands[i+1].insert(todo+r1);
					}
					if(todo - r1 >= 1 && !seen[todo-r1]){
						cands[i+1].insert(todo-r1);
					}
				}
				if(i - 1 >= 1 && !use[i-1]){
					int r1 = r[i-1];
					if(todo + r1 <= n && !seen[todo+r1]){
						cands[i-1].insert(todo+r1);
					}
					if(todo - r1 >= 1 && !seen[todo-r1]){
						cands[i-1].insert(todo-r1);
					}
				}
			}
			if(int(cands[i].size()) == 1){
				int todo = *cands[i].begin();
				for(int j = 1; j <= n; ++j){
					if(cands[j].count(todo)){
						cands[j].erase(todo);
					}
				}
			}
		}
	}
}

Compilation message (stderr)

xylophone.cpp:5:12: warning: 'A' defined but not used [-Wunused-variable]
    5 | static int A[5000];
      |            ^

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