oj.uz

Submission #39909

# Submission time Handle Problem Language Result Execution time Memory
39909 2018-01-24T09:50:08 Z 5ak0 OGLEDALA (COI15_ogledala) C++14
19 / 100
 297 ms 23112 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

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 <= MAXN; ++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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 8 ms 4368 KB Output is correct
3 Correct 199 ms 7008 KB Output is correct
4 Correct 180 ms 7008 KB Output is correct
5 Correct 240 ms 11496 KB Output is correct
6 Correct 297 ms 12024 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 23112 KB Output is correct
2 Correct 174 ms 23112 KB Output is correct
3 Incorrect 243 ms 23112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 23112 KB Output isn't correct
2 Halted 0 ms 0 KB -