oj.uz

답안 #618213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
618213 2022-08-02T03:14:48 Z logTheorist OGLEDALA (COI15_ogledala) C++17
100 / 100
 2574 ms 199856 KB 
#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

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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 49 ms 2392 KB Output is correct
4 Correct 37 ms 2544 KB Output is correct
5 Correct 56 ms 7300 KB Output is correct
6 Correct 67 ms 7384 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 672 KB Output is correct
2 Correct 29 ms 640 KB Output is correct
3 Correct 891 ms 198208 KB Output is correct
4 Correct 886 ms 199780 KB Output is correct
5 Correct 997 ms 199776 KB Output is correct
6 Correct 1004 ms 199784 KB Output is correct

Subtask #3
59.0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1086 ms 99732 KB Output is correct
2 Correct 1038 ms 100944 KB Output is correct
3 Correct 1735 ms 199652 KB Output is correct
4 Correct 1727 ms 199844 KB Output is correct
5 Correct 2574 ms 199800 KB Output is correct
6 Correct 2521 ms 199856 KB Output is correct