oj.uz

Submission #1053195

# Submission time Handle Problem Language Result Execution time Memory
1053195 2024-08-11T09:37:55 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 54784 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];

    vector<int> prev = a;
    while (nowt != t && !ok) {
      shuffle();
      if (prev == a) ok = 1;
      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 1102 ms 43400 KB Output is correct
2 Correct 1114 ms 42888 KB Output is correct
3 Correct 1048 ms 41296 KB Output is correct
4 Correct 1053 ms 40124 KB Output is correct
5 Correct 1121 ms 42516 KB Output is correct
6 Correct 1089 ms 40276 KB Output is correct
7 Correct 1131 ms 42656 KB Output is correct
8 Correct 1117 ms 40596 KB Output is correct
9 Correct 1046 ms 40060 KB Output is correct
10 Correct 1060 ms 40908 KB Output is correct
11 Correct 1066 ms 40716 KB Output is correct
12 Correct 1047 ms 39504 KB Output is correct
13 Correct 1072 ms 40764 KB Output is correct
14 Correct 1164 ms 41556 KB Output is correct
15 Correct 1176 ms 41832 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1117 ms 40040 KB Output is correct
18 Correct 1078 ms 39844 KB Output is correct
19 Correct 0 ms 452 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 3069 ms 54784 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 3071 ms 9640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 43400 KB Output is correct
2 Correct 1114 ms 42888 KB Output is correct
3 Correct 1048 ms 41296 KB Output is correct
4 Correct 1053 ms 40124 KB Output is correct
5 Correct 1121 ms 42516 KB Output is correct
6 Correct 1089 ms 40276 KB Output is correct
7 Correct 1131 ms 42656 KB Output is correct
8 Correct 1117 ms 40596 KB Output is correct
9 Correct 1046 ms 40060 KB Output is correct
10 Correct 1060 ms 40908 KB Output is correct
11 Correct 1066 ms 40716 KB Output is correct
12 Correct 1047 ms 39504 KB Output is correct
13 Correct 1072 ms 40764 KB Output is correct
14 Correct 1164 ms 41556 KB Output is correct
15 Correct 1176 ms 41832 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1117 ms 40040 KB Output is correct
18 Correct 1078 ms 39844 KB Output is correct
19 Correct 0 ms 452 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3069 ms 54784 KB Time limit exceeded
22 Halted 0 ms 0 KB -