Submission #39908

#	Time	Username	Problem	Language	Result	Execution time	Memory
39908		5ak0	OGLEDALA (COI15_ogledala)	C++14	19 / 100	533 ms	41856 KiB

ogledala

/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 3e5 + 10;

set <pair<int, pii> > s;
int m, n, q;
int a[MAXN], ans[MAXN];

int main(){
    cin >> m >> n >> q;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        ans[i] = a[i];
    }
    sort (a + 1, a + n + 1);
    a[n + 1] = m + 1;
    for (int i = 0; i <= n; ++i){
        if (a[i] + 1 == a[i + 1])
            continue;
        s.insert({-((a[i + 1] - 1) - (a[i] + 1)), {a[i] + 1, a[i + 1] - 1}});
    }
    for (int i = n + 1; i <= m; ++i){
        pair <int, pii> kek = *s.begin();
        int mid = (kek.sc.fr + kek.sc.sc) / 2;
        if (kek.sc.fr <= mid - 1)
            s.insert({-((mid - 1) - (kek.sc.fr)), {kek.sc.fr, mid - 1}});
        if (mid + 1 <= kek.sc.sc)
            s.insert({-((kek.sc.sc) - (mid + 1)), {mid + 1, kek.sc.sc}});
        ans[i] = mid;
        s.erase(kek);
//        cout << i << ":\n";
//        for (auto to : s)
//            cout << to.sc.fr << " " << to.sc.sc << "\n";
        //cerr << kek.fr << " " << kek.sc << " " << mid << "\n";
    }
    for (int i = 1; i <= q; ++i){
        int x;
        cin >> x;
        cout << ans[x] << "\n";
    }
    return 0;
}

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