oj.uz

Submission #861197

# Submission time Handle Problem Language Result Execution time Memory
861197 2023-10-15T16:03:29 Z vgtcross Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 27216 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

void solve() {
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n), b(n);
    for (int &i : a) cin >> i;
    
    vector<array<int, 3>> que(q);
    for (int i = 0; i < q; ++i) {
        cin >> que[i][0] >> que[i][1];
        que[i][2] = i;
    }
    
    sort(que.begin(), que.end());
    vector<int> ans(q);
    
    int j = 0;
    for (int i = 0; true; ++i) {
        while (j < q && que[j][0] == i) {
            ans[que[j][2]] = a[que[j][1]-1];
            ++j;
        }
        
        int x = 0, y = 0, z = n/2;
        while (y < n/2 && z < n) {
            if (a[y] < a[z]) b[x++] = a[y++];
            else b[x++] = a[z++];
        }
        
        while (y < n/2) b[x++] = a[y++];
        while (z < n) b[x++] = a[z++];
        if (a == b) break;
        a = b;
    }
    
    while (j < q) {
        ans[que[j][2]] = a[que[j][1]-1];
        ++j;
    }
    
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 19876 KB Output is correct
2 Correct 302 ms 27216 KB Output is correct
3 Correct 278 ms 26336 KB Output is correct
4 Correct 279 ms 25168 KB Output is correct
5 Correct 294 ms 26992 KB Output is correct
6 Correct 271 ms 25536 KB Output is correct
7 Correct 289 ms 26948 KB Output is correct
8 Correct 276 ms 25680 KB Output is correct
9 Correct 278 ms 25304 KB Output is correct
10 Correct 279 ms 25672 KB Output is correct
11 Correct 277 ms 25796 KB Output is correct
12 Correct 293 ms 24660 KB Output is correct
13 Correct 284 ms 25428 KB Output is correct
14 Correct 280 ms 26292 KB Output is correct
15 Correct 286 ms 26096 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 263 ms 25068 KB Output is correct
18 Correct 283 ms 25144 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3017 ms 17600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3008 ms 2680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 19876 KB Output is correct
2 Correct 302 ms 27216 KB Output is correct
3 Correct 278 ms 26336 KB Output is correct
4 Correct 279 ms 25168 KB Output is correct
5 Correct 294 ms 26992 KB Output is correct
6 Correct 271 ms 25536 KB Output is correct
7 Correct 289 ms 26948 KB Output is correct
8 Correct 276 ms 25680 KB Output is correct
9 Correct 278 ms 25304 KB Output is correct
10 Correct 279 ms 25672 KB Output is correct
11 Correct 277 ms 25796 KB Output is correct
12 Correct 293 ms 24660 KB Output is correct
13 Correct 284 ms 25428 KB Output is correct
14 Correct 280 ms 26292 KB Output is correct
15 Correct 286 ms 26096 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 263 ms 25068 KB Output is correct
18 Correct 283 ms 25144 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3017 ms 17600 KB Time limit exceeded
22 Halted 0 ms 0 KB -