Submission #1158276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158276		Doncho_Bonboncho	OGLEDALA (COI15_ogledala)	C++20	19 / 100	40 ms	7092 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;
#define int ll
const ll mod = 1e9 + 7;
const int MAX_N = 1e6 + 42;

struct Gap {
    ll len;
    int L, R;
    Gap(ll l, int _L, int _R) : len(l), L(_L), R(_R) {}
};

struct GapComp {
    bool operator()(const Gap &a, const Gap &b) const {
        if(a.len == b.len) return a.L > b.L;
        return a.len < b.len;
    }
};

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

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

    priority_queue<Gap, vector<Gap>, GapComp> pq;
    for (int i = 1; i <= n+1; i++){
        ll d = a[i] - a[i-1] - 1;
        if(d > 0){
            pq.push(Gap(d, a[i-1], a[i]));
        }
    }

    vector<int> ans(m+1, 0);
    for (int i = 1; i <= n; i++){
        ans[i] = a[i];
    }

    for (int k = n+1; k <= m; k++){
        Gap cur = pq.top();
        pq.pop();
        int pos;
        if(cur.len % 2 == 0) pos = cur.L + cur.len/2;
        else pos = cur.L + (cur.len+1)/2;
        ans[k] = pos;

        ll leftLen = pos - cur.L - 1;
        ll rightLen = cur.R - pos - 1;
        if(leftLen > 0) {
            pq.push(Gap(leftLen, cur.L, pos));
        }
        if(rightLen > 0) {
            pq.push(Gap(rightLen, pos, cur.R));
        }
    }

    for (int i = 0; i < q; i++){
        int Bi;
        cin >> Bi;
        if(Bi <= n) cout << a[Bi] << "\n";
        else cout << ans[Bi] << "\n";
    }

    return 0;
}

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