oj.uz

Submission #894258

# Submission time Handle Problem Language Result Execution time Memory
894258 2023-12-28T03:08:24 Z box The Collection Game (BOI21_swaps) C++17
100 / 100
 5 ms 1208 KB 
/*
https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
*/
#include <bits/stdc++.h>
using namespace std;
 
#define ar array
#define sz(v) static_cast<int>(v.size())
#define all(v) (v).begin(), (v).end()
typedef pair<int, int> pi;
typedef long long ll;
typedef vector<int> vi;
 
#if 0
 
void solve(int n, int v);
void schedule(int i, int j);
vi visit();
void answer(vi v);
 
#else
 
#include "swaps.h"
 
#endif
 
void solve(int n, int v) {
  vi p(n);
  iota(all(p), 1);
 
  vector<pair<int, int>> t;
  auto sch = [&](int i, int j) {
    schedule(p[i], p[j]);
    t.push_back({i, j});
  };
  auto vis = [&]() {
    if (sz(t)) {
      vi v = visit();
      for (int h = 0; h < sz(t); h++)
        if (!v[h]) {
          auto [i, j] = t[h];
          swap(p[i], p[j]);
        }
      t.clear();
    }
  };
  for (int p = 1; p < n; p *= 2)
    for (int k = p; k >= 1; k /= 2) {
      for (int j = k % p; j < n - k; j += k * 2)
        for (int i = 0; i < min(k, n - j - k); i++)
          if ((i + j) / (p * 2) == (i + j + k) / (p * 2)) sch(i + j, i + j + k);
      vis();
    }
  answer(p);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 440 KB Correct
3 Correct 2 ms 436 KB Correct
4 Correct 4 ms 452 KB Correct
5 Correct 3 ms 700 KB Correct
6 Correct 4 ms 456 KB Correct
7 Correct 3 ms 448 KB Correct
8 Correct 3 ms 448 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 432 KB Correct
3 Correct 2 ms 440 KB Correct
4 Correct 3 ms 452 KB Correct
5 Correct 3 ms 456 KB Correct
6 Correct 3 ms 700 KB Correct
7 Correct 3 ms 952 KB Correct
8 Correct 3 ms 452 KB Correct
9 Correct 3 ms 452 KB Correct
10 Correct 3 ms 452 KB Correct
11 Correct 3 ms 456 KB Correct
12 Correct 3 ms 452 KB Correct
13 Correct 3 ms 704 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 432 KB Correct

Subtask #3-2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 432 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 1 ms 440 KB Correct

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 440 KB Correct
3 Correct 1 ms 600 KB Correct
4 Correct 3 ms 452 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 440 KB Correct
3 Correct 1 ms 600 KB Correct
4 Correct 3 ms 452 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 1 ms 440 KB Correct
7 Correct 2 ms 436 KB Correct
8 Correct 4 ms 452 KB Correct
9 Correct 3 ms 452 KB Correct
10 Correct 3 ms 704 KB Correct
11 Correct 3 ms 700 KB Correct
12 Correct 4 ms 448 KB Correct
13 Correct 1 ms 344 KB Correct
14 Correct 1 ms 432 KB Correct
15 Correct 1 ms 444 KB Correct
16 Correct 3 ms 624 KB Correct

Subtask #5-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 1 ms 436 KB Correct
4 Correct 3 ms 700 KB Correct
5 Correct 3 ms 448 KB Correct

Subtask #5-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 1 ms 436 KB Correct
4 Correct 3 ms 700 KB Correct
5 Correct 3 ms 448 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 1 ms 432 KB Correct
8 Correct 2 ms 436 KB Correct
9 Correct 3 ms 448 KB Correct
10 Correct 3 ms 444 KB Correct
11 Correct 3 ms 448 KB Correct
12 Correct 4 ms 448 KB Correct
13 Correct 4 ms 456 KB Correct
14 Correct 3 ms 456 KB Correct
15 Correct 3 ms 708 KB Correct
16 Correct 3 ms 452 KB Correct
17 Correct 3 ms 448 KB Correct
18 Correct 3 ms 448 KB Correct
19 Correct 0 ms 344 KB Correct
20 Correct 1 ms 436 KB Correct
21 Correct 1 ms 436 KB Correct
22 Correct 3 ms 876 KB Correct
23 Correct 3 ms 460 KB Correct

Subtask #6-1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 2 ms 440 KB Correct
4 Correct 3 ms 452 KB Correct
5 Correct 4 ms 700 KB Correct
6 Correct 3 ms 616 KB Correct

Subtask #6-2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 2 ms 440 KB Correct
4 Correct 3 ms 452 KB Correct
5 Correct 4 ms 700 KB Correct
6 Correct 3 ms 616 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 1 ms 436 KB Correct
9 Correct 1 ms 440 KB Correct
10 Correct 3 ms 456 KB Correct
11 Correct 4 ms 444 KB Correct
12 Correct 3 ms 444 KB Correct
13 Correct 3 ms 448 KB Correct
14 Correct 5 ms 452 KB Correct
15 Correct 3 ms 452 KB Correct
16 Correct 3 ms 452 KB Correct
17 Correct 4 ms 456 KB Correct
18 Correct 3 ms 956 KB Correct
19 Correct 3 ms 456 KB Correct
20 Correct 0 ms 344 KB Correct
21 Correct 1 ms 608 KB Correct
22 Correct 2 ms 436 KB Correct
23 Correct 4 ms 596 KB Correct
24 Correct 3 ms 452 KB Correct
25 Correct 5 ms 424 KB Correct

Subtask #7-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 2 ms 612 KB Correct
4 Correct 3 ms 708 KB Correct
5 Correct 4 ms 448 KB Correct
6 Correct 3 ms 676 KB Correct
7 Correct 3 ms 668 KB Correct

Subtask #7-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 2 ms 612 KB Correct
4 Correct 3 ms 708 KB Correct
5 Correct 4 ms 448 KB Correct
6 Correct 3 ms 676 KB Correct
7 Correct 3 ms 668 KB Correct
8 Correct 0 ms 344 KB Correct
9 Correct 0 ms 344 KB Correct
10 Correct 1 ms 436 KB Correct
11 Correct 2 ms 692 KB Correct
12 Correct 3 ms 444 KB Correct
13 Correct 3 ms 456 KB Correct
14 Correct 3 ms 700 KB Correct
15 Correct 3 ms 452 KB Correct
16 Correct 3 ms 700 KB Correct
17 Correct 3 ms 1208 KB Correct
18 Correct 3 ms 452 KB Correct
19 Correct 3 ms 456 KB Correct
20 Correct 3 ms 708 KB Correct
21 Correct 4 ms 856 KB Correct
22 Correct 0 ms 344 KB Correct
23 Correct 1 ms 432 KB Correct
24 Correct 2 ms 440 KB Correct
25 Correct 3 ms 956 KB Correct
26 Correct 3 ms 456 KB Correct
27 Correct 3 ms 428 KB Correct
28 Correct 3 ms 588 KB Correct