oj.uz

Submission #39912

# Submission time Handle Problem Language Result Execution time Memory
39912 2018-01-24T09:58:33 Z 5ak0 OGLEDALA (COI15_ogledala) C++14
41 / 100
 445 ms 25456 KB 
/*
ID: 5ak0
PROG:
LANG: C++11
*/

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

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];

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 <= min(m, MAXN - 1); ++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;
}

Compilation message

ogledala.cpp:24:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6712 KB Output is correct
2 Correct 1 ms 6712 KB Output is correct
3 Correct 113 ms 9352 KB Output is correct
4 Correct 138 ms 9352 KB Output is correct
5 Correct 302 ms 13840 KB Output is correct
6 Correct 234 ms 14368 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 25456 KB Output is correct
2 Correct 166 ms 25456 KB Output is correct
3 Correct 445 ms 25456 KB Output is correct
4 Correct 429 ms 25456 KB Output is correct
5 Correct 431 ms 25456 KB Output is correct
6 Correct 393 ms 25456 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 244 ms 25456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -