oj.uz

Submission #846253

# Submission time Handle Problem Language Result Execution time Memory
846253 2023-09-07T12:57:15 Z vjudge1 OGLEDALA (COI15_ogledala) C++17
41 / 100
 2094 ms 37156 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 644 ms 4992 KB Output is correct
4 Correct 602 ms 5144 KB Output is correct
5 Correct 1362 ms 16708 KB Output is correct
6 Correct 1393 ms 14892 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2094 ms 23684 KB Output is correct
2 Correct 2048 ms 24984 KB Output is correct
3 Correct 1423 ms 23752 KB Output is correct
4 Correct 1442 ms 22612 KB Output is correct
5 Correct 1377 ms 24772 KB Output is correct
6 Correct 1383 ms 23444 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 1418 ms 37156 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -