Submission #618213

#	Time	Username	Problem	Language	Result	Execution time	Memory
618213		logTheorist	OGLEDALA (COI15_ogledala)	C++17	100 / 100	2574 ms	199856 KiB

ogledala

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

using ll	= long long;
using pll	= pair<ll, ll>;

#define fi	first
#define se	second

const int maxN	= 1e5 + 5;

const ll INF	= 1e18;

ll M, N, Q;
ll A[maxN], B[maxN];

struct Segment {
	ll len, cnt, initPos;

	Segment(ll len, ll cnt, ll initPos) :
		len(len), cnt(cnt), initPos(initPos)
	{}

	bool operator < (const Segment &other) const {
		return make_pair(-len, initPos) < make_pair(-other.len, other.initPos);
	}
};

void split(ll len, vector<pll> &V) {
	if (len == 0) return;

	// all possible lengths can form pairs of {p, p-1}
	V.push_back({len+1, 0});
	V.push_back({len, 1});

	for (ll ptr = 0; ; ptr += 2) {
		ll big = V[ptr].fi / 2;
		ll small = (V[ptr+1].fi - 1) / 2;

		//cout << V[ptr].fi << ' ' << V[ptr].se << '\n';
		//cout << V[ptr+1].fi << ' ' << V[ptr+1].se << '\n';

		ll Bcnt = V[ptr].se, Scnt = V[ptr+1].se;

		if ((V[ptr].fi - 1) / 2 == big) {
			Bcnt += V[ptr].se;
		} else {
			Scnt += V[ptr].se;
		}
		if (V[ptr+1].fi / 2 == big) {
			Bcnt += V[ptr+1].se;
		} else {
			Scnt += V[ptr+1].se;
		}

		V.push_back({big, Bcnt});
		V.push_back({small, Scnt});

		if (big == 0 && small == 0) break;
	}

	while (!V.empty() && (!V.back().fi || !V.back().se)) V.pop_back();
	ll one = 0;
	while (!V.empty() && (V.back().fi == 1)) {
		one += V.back().se;
		V.pop_back();
	}
	if (one) V.push_back({1, one});

	//for (auto &[len, cnt] : V) {cout << len << ' ' << cnt << '\n';}
}

ll findPos(ll findLen, ll l, ll r, ll val) {
	//cerr << "findPos(" << findLen << ", " << l << ", " << r << ", " << val << ")\n";
	if (r - l + 1 == findLen) {return l + (r-l)/2;}

	vector<pll> tmp;
	ll m = l + (r-l)/2;
	split(m-l, tmp);
	ll findCnt = 0;
	for (auto &[len, cnt] : tmp) {
		if (len == findLen) {findCnt += cnt; break;}
	}
	//cerr << findCnt << '\n';

	if (val <= findCnt) {
		return findPos(findLen, l, m-1, val);
	} else {
		return findPos(findLen, m+1, r, val-findCnt);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> M >> N >> Q;
	A[0] = 0, A[N+1] = M+1;
	for (ll i = 1; i <= N; i++) {
		cin >> A[i];
	}
	vector<Segment> S;
	for (ll i = 1; i <= N+1; i++) {
		vector<pll> tmp;
		split(A[i] - A[i-1] - 1, tmp);
		for (auto &[len, cnt] : tmp) {
			if (len && cnt) S.push_back(Segment(len, cnt, i));
		}
	}
	sort(S.begin(), S.end());
	for (auto &[len, cnt, idx] : S) {
		//cerr << len << ' ' << cnt << ' ' << idx << '\n';
	}

	for (ll i = 1; i <= Q; i++) {
		cin >> B[i];
	}
	B[Q+1] = INF;
	
	ll qptr = 1;
	for (; B[qptr] <= N; qptr++) {
		cout << A[B[qptr]] << '\n';
	}
	ll cur = N+1;
	for (auto &[len, cnt, idx] : S) {
		//cout << "! " << cur << '\n';
		for (; B[qptr] <= cur + cnt - 1; qptr++) {
			cout << findPos(len, A[idx-1]+1, A[idx]-1, B[qptr] - cur + 1) << '\n';
		}
		cur += cnt;
	}
}

Compilation message (stderr)

ogledala.cpp: In function 'int main()':
ogledala.cpp:110:13: warning: unused structured binding declaration [-Wunused-variable]
  110 |  for (auto &[len, cnt, idx] : S) {
      |             ^~~~~~~~~~~~~~~

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