oj.uz

Submission #1053212

# Submission time Handle Problem Language Result Execution time Memory
1053212 2024-08-11T09:47:17 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 40416 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << endl;
void g(vector<int>&a) {
  for (auto el : a) cout << el << ", ";
  cout << endl;
}

void solve() {
  int n,q;cin>>n>>q;

  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<tuple<int, int, int>> queries(q);
  for (int i = 0; i < q; i++) {
    int t,j;cin>>t>>j;j--;
    queries[i] = {t,j,i};
  }

  sort(all(queries));
  vector<int> ans(q);

  function<void()> shuffle = [&]() {
    vector<int> left, right;
    for (int i = 0; i < n; i++) {
      if (i < n/2) left.push_back(a[i]);
      else right.push_back(a[i]);
    }

    left.push_back(1e18);
    right.push_back(1e18);

    reverse(all(left));
    reverse(all(right));

    vector<int> cur;
    for (int i = 0; i < n; i++) {
      if (left.back() < right.back()) {
        cur.push_back(left.back());
        left.pop_back();
      }
      else {
        cur.push_back(right.back());
        right.pop_back();
      }
    }

    a = cur;
  };

  int nowt = 0;
  bool ok = 0;
  for (int i = 0; i < q; i++) {
    auto [t, idx, cid] = queries[i];

    while (nowt != t && !ok) {
      vector<int> prev = a;
      shuffle();
      if (prev == a) ok = 1;
      // g(a);
      nowt++;
    }

    // g(a);
    ans[cid] = a[idx];
  }

  for (auto el : ans) cout << el << endl;
}

int32_t main() {
  ios_base::sync_with_stdio(0);cin.tie(0);
  int t=1;
  while(t--) solve();

  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 35476 KB Output is correct
2 Correct 990 ms 35664 KB Output is correct
3 Correct 979 ms 34128 KB Output is correct
4 Correct 1040 ms 33872 KB Output is correct
5 Correct 997 ms 35540 KB Output is correct
6 Correct 971 ms 33828 KB Output is correct
7 Correct 1040 ms 35408 KB Output is correct
8 Correct 984 ms 34384 KB Output is correct
9 Correct 980 ms 33876 KB Output is correct
10 Correct 977 ms 34384 KB Output is correct
11 Correct 984 ms 34348 KB Output is correct
12 Correct 944 ms 33856 KB Output is correct
13 Correct 950 ms 34572 KB Output is correct
14 Correct 1024 ms 34992 KB Output is correct
15 Correct 990 ms 35484 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 952 ms 34428 KB Output is correct
18 Correct 962 ms 34244 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 3083 ms 40416 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 3053 ms 8116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 35476 KB Output is correct
2 Correct 990 ms 35664 KB Output is correct
3 Correct 979 ms 34128 KB Output is correct
4 Correct 1040 ms 33872 KB Output is correct
5 Correct 997 ms 35540 KB Output is correct
6 Correct 971 ms 33828 KB Output is correct
7 Correct 1040 ms 35408 KB Output is correct
8 Correct 984 ms 34384 KB Output is correct
9 Correct 980 ms 33876 KB Output is correct
10 Correct 977 ms 34384 KB Output is correct
11 Correct 984 ms 34348 KB Output is correct
12 Correct 944 ms 33856 KB Output is correct
13 Correct 950 ms 34572 KB Output is correct
14 Correct 1024 ms 34992 KB Output is correct
15 Correct 990 ms 35484 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 952 ms 34428 KB Output is correct
18 Correct 962 ms 34244 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 3083 ms 40416 KB Time limit exceeded
22 Halted 0 ms 0 KB -