Submission #387268

#	Time	Username	Problem	Language	Result	Execution time	Memory
387268		sinamhdv	OGLEDALA (COI15_ogledala)	C++11	19 / 100	4094 ms	132112 KiB

ogledala

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100

ll m;
int n, q;
ll a[MAXN];
vector<pair<pll, ll>> segs;
vector<ll> ps;

void clean(vector<pll> &vec)
{
	sort(all(vec));
	vector<pll> res;
	int n = vec.size();
	for (int i = 0; i < n;)
	{
		int j;
		ll cnt = 0;
		for (j = i; j < n && vec[j].fr == vec[i].fr; j++)
			cnt += vec[j].sc;
		res.pb({vec[i].fr, cnt});
		i = j;
	}
	vec = res;
}

vector<pll> findsegs(ll n)
{
	if (n == 1) return {{1, 1}};
	if (n == 2) return {{2, 1}, {1, 1}};
	if (n == 4) return {{4, 1}, {2, 1}, {1, 2}};
	if (n == 6) return {{6, 1}, {3, 1}, {2, 1}, {1, 3}};

	if (n % 2)
	{
		vector<pll> res = findsegs(n/2);
		for (pll &p : res) p.sc *= 2;
		res.pb({n, 1});
		return res;
	}
	
	if (n % 4) 	// 4k + 2
	{
		vector<pll> res = findsegs(n/4 - 1);
		vector<pll> kres = findsegs(n/4);
		for (pll p : kres)
			res.pb({p.fr, p.sc * 3});
		res.pb({n/2, 1});
		res.pb({n/2 - 1, 1});
		res.pb({n, 1});
		clean(res);
		return res;
	}

	// 4k
	vector<pll> res = findsegs(n/4);
	vector<pll> k1res = findsegs(n/4 - 1);
	for (pll p : k1res)
		res.pb({p.fr, p.sc * 3});
	res.pb({n/2, 1});
	res.pb({n/2 - 1, 1});
	res.pb({n, 1});
	clean(res);
	return res;
}

bool cmp(pair<pll, ll> x, pair<pll, ll> y)
{
	if (x.fr.fr == y.fr.fr) return x.fr.sc < y.fr.sc;
	return x.fr.fr > y.fr.fr;
}

ll getcnt(ll n, ll k)
{
	if (n == k)
		return 1;
	if (n == 1) return (k == 1 ? 1 : 0);
	if (n == 2) return (k <= 2 ? 1 : 0);
	if (n == 4) return (k == 1 ? 2 : (k == 2 || k == 4 ? 1 : 0));
	if (n == 6) return (k == 1 ? 3 : (k == 2 || k == 3 || k == 6 ? 1 : 0));

	if (n % 2)
		return getcnt(n/2, k) * 2;

	if (k == n/2 || k == (n + 1)/2 - 1)
		return 1;

	if (n % 4)	// 4k + 2
		return getcnt(n/4 - 1, k) + getcnt(n/4, k) * 3;

	// 4k
	return getcnt(n/4, k) + getcnt(n/4 - 1, k) * 3;
}

ll findmid(ll n, ll l, ll k, ll len)
{
	if (n == 1) return l;
	if (n == 2) return (len == 1 ? l + 1 : l);
	if (n == len)
	{
		ll r = l + n - 1;
		return (r + l) / 2;
	}
	ll p = getcnt((n + 1)/2 - 1, len);
	if (p >= k)
		return findmid((n + 1)/2 - 1, l, k, len);
	return findmid(n/2, l + (n + 1)/2, k - p, len);
}

int32_t main(void)
{
	fast_io;
	cin >> m >> n >> q;
	FOR(i, 1, n + 1)
	{
		cin >> a[i];
		if (a[i] > a[i - 1] + 1)
		{
			vector<pll> vec = findsegs(a[i] - a[i - 1] - 1);
			for (pll p : vec)
				segs.pb({{p.fr, i}, p.sc});
		}
	}
	if (a[n] < m)
	{
		vector<pll> vec = findsegs(m - a[n]);
		for (pll p : vec)
			segs.pb({{p.fr, n + 1}, p.sc});
	}
	a[n + 1] = m + 1;

	sort(all(segs), cmp);
	ps.pb(0);
	for (auto p : segs)
		ps.pb(ps.back() + p.sc);

	/*
	for (auto p : segs)
		cout << "((" << p.fr.fr << ", " << p.fr.sc << "), " << p.sc << ")\n";
	dbgr(ps.begin(), ps.end());
	*/

	while (q--)
	{
		ll x;
		cin >> x;
		if (x <= n)
		{
			cout << a[x] << endl;
			continue;
		}
		x -= n;
		int pos = lower_bound(all(ps), x) - ps.begin();
		ll ord = x - ps[pos - 1];
		auto p = segs[pos - 1];
		ll mainlen = a[p.fr.sc] - a[p.fr.sc - 1] - 1;
		ll len = p.fr.fr;

		cout << findmid(mainlen, a[p.fr.sc - 1] + 1, ord, len) << endl;
	}

	return 0;
}

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