oj.uz

Submission #830409

# Submission time Handle Problem Language Result Execution time Memory
830409 2023-08-19T06:13:35 Z PoonYaPat Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 29052 KB 
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> tu;

int cnt,n,q,ans[1000005];
vector<int> v;
bool same=false;
vector<tu> qq; //time, order of array, idx of answer

void shuffle() {
    vector<int> temp;
    int hlf=n/2;

    int l=0, r=hlf;
    while (l<hlf && r<n) {
        if (v[l]<v[r]) temp.push_back(v[l++]);
        else temp.push_back(v[r++]);
    }

    while (l<hlf) temp.push_back(v[l++]);
    while (r<n) temp.push_back(v[r++]);

    same=true;
    for (int i=0; i<n; ++i) if (temp[i]!=v[i]) same=false;
    swap(temp,v);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    for (int i=0; i<n; ++i) {
        int x; cin>>x;
        v.push_back(x);
    }

    for (int i=0; i<q; ++i) {
        int a,b; cin>>a>>b;
        qq.push_back(tu(a,b-1,i));
    }
    sort(qq.begin(),qq.end());

    int idx=0;

    while (idx<q && get<0>(qq[idx])==cnt) {
        ans[get<2>(qq[idx])]=v[get<1>(qq[idx])];
        ++idx;
    }

    while (!same) {
        shuffle();
        ++cnt;

        while (idx<q && get<0>(qq[idx])==cnt) {
            ans[get<2>(qq[idx])]=v[get<1>(qq[idx])];
            ++idx;
        }
        if (idx==q) break;
    }

    while (idx<q) {
        ans[get<2>(qq[idx])]=v[get<1>(qq[idx])];
        ++idx;
    }
    
    for (int i=0; i<q; ++i) cout<<ans[i]<<"\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 27736 KB Output is correct
2 Correct 274 ms 27276 KB Output is correct
3 Correct 262 ms 26400 KB Output is correct
4 Correct 263 ms 25200 KB Output is correct
5 Correct 278 ms 26980 KB Output is correct
6 Correct 268 ms 25448 KB Output is correct
7 Correct 271 ms 27148 KB Output is correct
8 Correct 258 ms 25628 KB Output is correct
9 Correct 260 ms 25244 KB Output is correct
10 Correct 258 ms 25808 KB Output is correct
11 Correct 257 ms 25648 KB Output is correct
12 Correct 255 ms 24748 KB Output is correct
13 Correct 262 ms 25544 KB Output is correct
14 Correct 272 ms 26348 KB Output is correct
15 Correct 268 ms 26212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 251 ms 25000 KB Output is correct
18 Correct 270 ms 24768 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 29052 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 3052 ms 4860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 27736 KB Output is correct
2 Correct 274 ms 27276 KB Output is correct
3 Correct 262 ms 26400 KB Output is correct
4 Correct 263 ms 25200 KB Output is correct
5 Correct 278 ms 26980 KB Output is correct
6 Correct 268 ms 25448 KB Output is correct
7 Correct 271 ms 27148 KB Output is correct
8 Correct 258 ms 25628 KB Output is correct
9 Correct 260 ms 25244 KB Output is correct
10 Correct 258 ms 25808 KB Output is correct
11 Correct 257 ms 25648 KB Output is correct
12 Correct 255 ms 24748 KB Output is correct
13 Correct 262 ms 25544 KB Output is correct
14 Correct 272 ms 26348 KB Output is correct
15 Correct 268 ms 26212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 251 ms 25000 KB Output is correct
18 Correct 270 ms 24768 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Execution timed out 3040 ms 29052 KB Time limit exceeded
22 Halted 0 ms 0 KB -