제출 #846253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846253		vjudge1	OGLEDALA (COI15_ogledala)	C++17	41 / 100	2094 ms	37156 KiB

ogledala

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif

void solve()
{
    int n, m, q; cin >> n >> m >> q;
    vector <int> vec(m +2);
    for(int i = 1; i <= m; i++) cin >> vec[i];
    vec[0] = 0;
    vec[m +1] = n +1;

    vector <int> anss;
    for(int i = 1; i <= m; i++) anss.emplace_back(vec[i]);

    priority_queue <tuple <int, int, int>> pq;
    for(int i = 1; i <= m +1; i++)
    {
        pq.emplace((vec[i] -1) - (vec[i -1] +1) +1, -(vec[i -1] +1), -(vec[i] -1));
    }

    while(!pq.empty() && anss.size() <= 300000)
    {
        auto [diff, l, r] = pq.top();
        l *= -1; r *= -1;
        cerr << diff << " " << l << " " << r << "\n";
        pq.pop();
        int mid = (r + l) / 2;
        anss.emplace_back((r + l) / 2);
        if(l <= mid -1) pq.emplace(((mid -1) - l +1), -l, -(mid -1));
        if(mid +1 <= r) pq.emplace((r - (mid +1) +1), -(mid +1), -r);
    }

    //for(int &i : anss) cout << i << " ";

    for(int i = 1; i <= q; i++)
    {
        int x; cin >> x;
        cout << anss[x -1] << "\n";
    }

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

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