Submission #1157849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157849		Doncho_Bonboncho	OGLEDALA (COI15_ogledala)	C++20	19 / 100	86 ms	19468 KiB

ogledala

#include <bits/stdc++.h>
#include <iostream>
#include <random>
#include <utility>
#include <variant>
#include <vector>
using namespace std;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define out( x ) #x << " = " << x << "  "
#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
const ll mod = 1e9 +7;
const int MAX_N = 1e6 + 42;

struct cmp {
	bool operator()(const std::pair<ll, int>& a, const std::pair<ll, int>& b) const {
		if(a.first != b.first)
			return a.first < b.first;
		return a.second > b.second;
	}
};

int main(){
#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	ll m, n, q;
	std::cin >> m >> n >> q;
	std::vector< int > a( n+2 );
	for( int i=1 ; i <= n ; i++ ) std::cin >> a[i];
	a[n+1] = m+1;

	std::set<std::pair< ll, int >, cmp > dist;
	for( int i=1 ; i <= n+1 ; i++ ){
		ll currDist = a[i] - a[i-1];
		dist.insert({ currDist-1, a[i-1] + 1 });
	}

	std::vector< ll > b( q );
	for( auto& j : b ) std::cin >> j;


	int ind = 0;
	while( ind < q and b[ind] <= n ) std::cout << a[ b[ind++] ] << endl;
	int currStep = n;
	while( ind < q ){

		for( auto j : dist) cerr << j.first << " " << j.second << endl;
		cerr << endl;


		currStep ++;
		auto curr = *( dist.rbegin() );
		cerr << out( curr.first ) << out( curr.second ) << out( b[ind] ) << out( currStep ) << endl;
		if( b[ind] == currStep ){
			ll currNas = curr.second + curr.first / 2LL;
			if( curr.first % 2 == 0 ) currNas -= 1;
			std::cout << currNas << endl;
			ind ++;
		}

		std::pair< ll, int > A = { (curr.first-1LL)/2, curr.second };
		std::pair< ll, int > B = { curr.first/2, curr.second + ( curr.first + 1LL ) /2LL };
		if( A.first ) dist.insert( A );
		if( B.first ) dist.insert( B );
		auto it = dist.find( curr );
		dist.erase( it );
	}

	return 0;
}

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