Submission #846370

#	Time	Username	Problem	Language	Result	Execution time	Memory
846370		vjudge1	OGLEDALA (COI15_ogledala)	C++17	41 / 100	2566 ms	524288 KiB

ogledala

#include <bits/stdc++.h>
#define lint long long
#define endl '\n'
#define pii pair<int, int>
#define pll pair<lint, lint>
#define For(i,n) for (int i = 0; i < n; i++)
#define FOR For(i, n)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

const lint N = 3e5+100;

struct Space {
	lint len; lint starti; lint stopi;
	bool operator <(const Space other) const {
		return len == other.len ? starti > other.starti : len < other.len;
	}
};

priority_queue<Space> spaces;
set<lint> bins;

map<lint, lint> res;

int main() {
	fastio;
	lint m,n,q; cin >> m >> n >> q;
	bins.insert(0);
	bins.insert(m+1);
	FOR {
		lint x; cin >> x;
		res[i+1] = x;
		bins.insert(x);
	}

	// construct spaces
	auto it = bins.begin(); lint pv = *it; it++;
	for (; it != bins.end(); it++) {
		lint v = *it;
		lint space = v-pv-1;
		//cerr << "adding space: " << space << " " << pv << " " << v << endl;
		spaces.push({space, pv, v});
		pv = v;
	}

	// save queries
	vector<lint> queries(q);
	lint mxq = 0; // greatest query
	For(i,q) {
		lint x; cin >> x; queries[i] = x;
		mxq = max(x, mxq);
		if (!res[x]) res[x] = 1;
	}

	for(int i = n+1; i <= mxq; i++) {
		// lady i arrives
		auto space = spaces.top();
		lint len = space.len;
		lint starti = space.starti;
		lint stopi = space.stopi;
		spaces.pop();
		lint nbin = (starti + stopi) / 2;
		//bins.insert(nbin);
		//cerr << "lady " << i << ": " << nbin << "  space=" << len << "=" << starti << "," << stopi << endl;
		if (res[i]) res[i] = nbin;
		//cerr << "adding space: " << nbin-starti-1 << " " << starti << " " << nbin << endl;
		spaces.push({ nbin-starti-1, starti, nbin });
		//cerr << "adding space: " << stopi-nbin-1 << " " << nbin << " " << stopi << endl;
		spaces.push({ stopi-nbin-1, nbin, stopi });
	}


	for (int lady : queries) cout << res[lady] << " ";
	cout << endl;
}

Compilation message (stderr)

ogledala.cpp: In function 'int main()':
ogledala.cpp:58:8: warning: unused variable 'len' [-Wunused-variable]
   58 |   lint len = space.len;
      |        ^~~

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