oj.uz

Submission #1005305

# Submission time Handle Problem Language Result Execution time Memory
1005305 2024-06-22T10:11:21 Z MohamedFaresNebili Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 20528 KB 
#include <bits/stdc++.h>

        using namespace std;

        int N, Q;
        vector<int> A;
        vector<array<int, 3>> query;
        int ans[1000005];

        int32_t main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            cin >> N >> Q; A.resize(N);
            for(int l = 0; l < N; l++)
                cin >> A[l];
            for(int l = 0; l < Q; l++) {
                int t, i; cin >> t >> i;
                query.push_back({t, l, --i});
            }
            sort(query.begin(), query.end());
            bool ok = false; int cur = 0, cnt = 1;
            while(cur < Q && query[cur][0] == 0) {
                ans[query[cur][1]] = A[query[cur][2]];
                cur++;
            }
            while(!ok) {
                ok = true;
                vector<int> B;
                int i = 0, j = N / 2;
                while(B.size() < N) {
                    if(i == N / 2)
                        B.push_back(A[j++]);
                    else if(j == N) B.push_back(A[i++]);
                    else {
                        if(A[i] < A[j])
                            B.push_back(A[i++]);
                        else {
                            B.push_back(A[j++]);
                            ok = false;
                        }
                    }
                }
                swap(A, B);
                while(cur < Q && (query[cur][0] == cnt || ok == true)) {
                    ans[query[cur][1]] = A[query[cur][2]];
                    cur++;
                }
                cnt++;
            }
            for(int l = 0; l < Q; l++)
                cout << ans[l] << "\n";
            return 0;
        }

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:30:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |                 while(B.size() < N) {
      |                       ~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 20396 KB Output is correct
2 Correct 250 ms 19900 KB Output is correct
3 Correct 223 ms 19116 KB Output is correct
4 Correct 219 ms 20144 KB Output is correct
5 Correct 250 ms 20400 KB Output is correct
6 Correct 233 ms 19116 KB Output is correct
7 Correct 248 ms 20528 KB Output is correct
8 Correct 241 ms 19340 KB Output is correct
9 Correct 247 ms 19880 KB Output is correct
10 Correct 276 ms 20116 KB Output is correct
11 Correct 244 ms 19344 KB Output is correct
12 Correct 246 ms 19236 KB Output is correct
13 Correct 248 ms 20048 KB Output is correct
14 Correct 250 ms 19744 KB Output is correct
15 Correct 257 ms 20004 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 242 ms 20004 KB Output is correct
18 Correct 240 ms 19184 KB Output is correct
19 Correct 0 ms 348 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 3054 ms 14812 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 3065 ms 4928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 20396 KB Output is correct
2 Correct 250 ms 19900 KB Output is correct
3 Correct 223 ms 19116 KB Output is correct
4 Correct 219 ms 20144 KB Output is correct
5 Correct 250 ms 20400 KB Output is correct
6 Correct 233 ms 19116 KB Output is correct
7 Correct 248 ms 20528 KB Output is correct
8 Correct 241 ms 19340 KB Output is correct
9 Correct 247 ms 19880 KB Output is correct
10 Correct 276 ms 20116 KB Output is correct
11 Correct 244 ms 19344 KB Output is correct
12 Correct 246 ms 19236 KB Output is correct
13 Correct 248 ms 20048 KB Output is correct
14 Correct 250 ms 19744 KB Output is correct
15 Correct 257 ms 20004 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 242 ms 20004 KB Output is correct
18 Correct 240 ms 19184 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3054 ms 14812 KB Time limit exceeded
22 Halted 0 ms 0 KB -