Submission #1159836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159836		vimo	OGLEDALA (COI15_ogledala)	C++20	19 / 100	59 ms	7608 KiB

ogledala

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

#define out(x) #x << " = " << x << " "
#ifndef LOCAL
#define endl "\n"
#define cerr \
	if (false) cerr
#define stdio(true) stdio(false)
#endif

const long long MAX_M = 1e6 + 10;
const long long INF = 1e9 + 10;

long long m, n, q;
long long ans[MAX_M];
long long arr[MAX_M];

signed main() {
	ios_base::sync_with_stdio(true);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> m >> n >> q;

	long long cnt = 1;
	for (long long i = 1; i <= n; i++) {
		long long x;
		cin >> x;
		arr[x] = i;
		ans[cnt] = x;
		cnt++;
	}

	priority_queue<pair<long long, long long>> pq;
	long long start = 1;
	for (long long i = 1; i <= m; i++) {
		if (arr[i] != 0) {
			if (i - 1 >= start) pq.push({i - start, -start});
			start = i + 1;
		} else if (i == m) {
			if (i >= start) pq.push({i - start + 1, -start});
		}
	}
	while (!pq.empty()) {
		auto curr = pq.top();
		pq.pop();
		long long st = (-curr.second);
		long long ed = (-curr.second) + curr.first - 1;
		long long x = (st + ed) / 2;

		// cerr << st << " " << ed << " " << x << " adding ";

		ans[cnt] = x;
		arr[x] = cnt;
		cnt++;

		if ((x - 1) - st + 1 >= 1) {
			pq.push({(x - 1) - st + 1, -st});
			// cerr << "(from " << st << " " << (x - 1) - st + 1 << ") ";
		}
		if ((ed - (x + 1) + 1) >= 1) {
			pq.push({(ed - (x + 1) + 1), -(x + 1)});
			// cerr << "(from " << x + 1 << " " << (ed - (x + 1) + 1) << ") ";
		}
		// cerr << endl;
	}

	for (long long i = 0; i < q; i++) {
		long long x;
		cin >> x;
		cout << ans[x] << endl;
	}

	return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59