oj.uz

Submission #971607

# Submission time Handle Problem Language Result Execution time Memory
971607 2024-04-29T04:25:19 Z nguyentunglam Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 56376 KB 
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 1e6 + 10;

int n, q;

int a[N], b[N], c[N], ans[N];

vector<pair<int, int> > query[N];

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> q;

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

  for(int i = 1; i <= q; i++) {
    int t, x; cin >> t >> x;
    query[min(n, t)].emplace_back(x, i);
  }

  b[n / 2 + 1] = c[n / 2 + 1] = 1e9;
  for(int turn = 0; turn <= n; turn++) {
//    for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
    for(auto &[x, i] : query[turn]) {
      ans[i] = a[x];
    }
    for(int i = 1; i <= n / 2; i++) b[i] = a[i];
    for(int i = n / 2 + 1; i <= n; i++) c[i - n / 2] = a[i];
//    for(int i = 1; i <= n / 2; i++) cout << b[i] << " "; cout << endl;
//    for(int i = 1; i <= n / 2; i++) cout << c[i] << " "; cout << endl;
    for(int i = 1, j = 1; i <= n / 2 || j <= n / 2; ) {
      if (b[i] < c[j]) a[i + j - 1] = b[i], i++;
      else a[i + j - 1] = c[j], j++;
    }
//    for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
  }

  for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:26:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 47444 KB Output is correct
2 Correct 173 ms 53932 KB Output is correct
3 Correct 162 ms 53336 KB Output is correct
4 Correct 162 ms 52280 KB Output is correct
5 Correct 159 ms 55036 KB Output is correct
6 Correct 157 ms 55036 KB Output is correct
7 Correct 178 ms 56376 KB Output is correct
8 Correct 153 ms 53840 KB Output is correct
9 Correct 149 ms 52708 KB Output is correct
10 Correct 150 ms 52308 KB Output is correct
11 Correct 148 ms 52948 KB Output is correct
12 Correct 147 ms 50180 KB Output is correct
13 Correct 153 ms 51620 KB Output is correct
14 Correct 158 ms 54148 KB Output is correct
15 Correct 159 ms 52140 KB Output is correct
16 Correct 8 ms 31324 KB Output is correct
17 Correct 151 ms 50812 KB Output is correct
18 Correct 152 ms 50348 KB Output is correct
19 Correct 6 ms 31324 KB Output is correct
20 Correct 7 ms 31340 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3030 ms 53016 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 3002 ms 33360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 47444 KB Output is correct
2 Correct 173 ms 53932 KB Output is correct
3 Correct 162 ms 53336 KB Output is correct
4 Correct 162 ms 52280 KB Output is correct
5 Correct 159 ms 55036 KB Output is correct
6 Correct 157 ms 55036 KB Output is correct
7 Correct 178 ms 56376 KB Output is correct
8 Correct 153 ms 53840 KB Output is correct
9 Correct 149 ms 52708 KB Output is correct
10 Correct 150 ms 52308 KB Output is correct
11 Correct 148 ms 52948 KB Output is correct
12 Correct 147 ms 50180 KB Output is correct
13 Correct 153 ms 51620 KB Output is correct
14 Correct 158 ms 54148 KB Output is correct
15 Correct 159 ms 52140 KB Output is correct
16 Correct 8 ms 31324 KB Output is correct
17 Correct 151 ms 50812 KB Output is correct
18 Correct 152 ms 50348 KB Output is correct
19 Correct 6 ms 31324 KB Output is correct
20 Correct 7 ms 31340 KB Output is correct
21 Execution timed out 3030 ms 53016 KB Time limit exceeded
22 Halted 0 ms 0 KB -