oj.uz

Submission #807546

# Submission time Handle Problem Language Result Execution time Memory
807546 2023-08-04T19:14:12 Z dong_liu The Collection Game (BOI21_swaps) C++17
100 / 100
 5 ms 424 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 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 364 KB Correct
5 Correct 3 ms 316 KB Correct
6 Correct 3 ms 320 KB Correct
7 Correct 3 ms 320 KB Correct
8 Correct 3 ms 320 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 1 ms 308 KB Correct
4 Correct 3 ms 304 KB Correct
5 Correct 4 ms 312 KB Correct
6 Correct 3 ms 312 KB Correct
7 Correct 3 ms 308 KB Correct
8 Correct 3 ms 316 KB Correct
9 Correct 3 ms 360 KB Correct
10 Correct 4 ms 420 KB Correct
11 Correct 4 ms 308 KB Correct
12 Correct 3 ms 308 KB Correct
13 Correct 4 ms 304 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct

Subtask #3-2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 0 ms 208 KB Correct
4 Correct 1 ms 208 KB Correct

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 304 KB Correct
3 Correct 1 ms 296 KB Correct
4 Correct 3 ms 316 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 304 KB Correct
3 Correct 1 ms 296 KB Correct
4 Correct 3 ms 316 KB Correct
5 Correct 0 ms 208 KB Correct
6 Correct 1 ms 208 KB Correct
7 Correct 2 ms 328 KB Correct
8 Correct 5 ms 308 KB Correct
9 Correct 3 ms 304 KB Correct
10 Correct 3 ms 304 KB Correct
11 Correct 3 ms 316 KB Correct
12 Correct 3 ms 312 KB Correct
13 Correct 1 ms 208 KB Correct
14 Correct 1 ms 208 KB Correct
15 Correct 2 ms 208 KB Correct
16 Correct 3 ms 408 KB Correct

Subtask #5-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 1 ms 208 KB Correct
4 Correct 3 ms 308 KB Correct
5 Correct 4 ms 288 KB Correct

Subtask #5-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 1 ms 208 KB Correct
4 Correct 3 ms 308 KB Correct
5 Correct 4 ms 288 KB Correct
6 Correct 0 ms 208 KB Correct
7 Correct 1 ms 208 KB Correct
8 Correct 2 ms 208 KB Correct
9 Correct 4 ms 308 KB Correct
10 Correct 4 ms 308 KB Correct
11 Correct 3 ms 312 KB Correct
12 Correct 4 ms 316 KB Correct
13 Correct 4 ms 312 KB Correct
14 Correct 3 ms 316 KB Correct
15 Correct 4 ms 312 KB Correct
16 Correct 3 ms 312 KB Correct
17 Correct 3 ms 312 KB Correct
18 Correct 4 ms 312 KB Correct
19 Correct 1 ms 208 KB Correct
20 Correct 1 ms 296 KB Correct
21 Correct 2 ms 208 KB Correct
22 Correct 3 ms 316 KB Correct
23 Correct 4 ms 292 KB Correct

Subtask #6-1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 3 ms 308 KB Correct
5 Correct 5 ms 316 KB Correct
6 Correct 4 ms 272 KB Correct

Subtask #6-2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 3 ms 308 KB Correct
5 Correct 5 ms 316 KB Correct
6 Correct 4 ms 272 KB Correct
7 Correct 0 ms 208 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 2 ms 304 KB Correct
10 Correct 3 ms 304 KB Correct
11 Correct 4 ms 312 KB Correct
12 Correct 3 ms 316 KB Correct
13 Correct 3 ms 308 KB Correct
14 Correct 4 ms 312 KB Correct
15 Correct 3 ms 308 KB Correct
16 Correct 4 ms 312 KB Correct
17 Correct 3 ms 316 KB Correct
18 Correct 3 ms 312 KB Correct
19 Correct 4 ms 308 KB Correct
20 Correct 0 ms 208 KB Correct
21 Correct 1 ms 208 KB Correct
22 Correct 2 ms 208 KB Correct
23 Correct 5 ms 424 KB Correct
24 Correct 3 ms 292 KB Correct
25 Correct 3 ms 272 KB Correct

Subtask #7-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 308 KB Correct
5 Correct 4 ms 312 KB Correct
6 Correct 5 ms 268 KB Correct
7 Correct 5 ms 288 KB Correct

Subtask #7-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 308 KB Correct
5 Correct 4 ms 312 KB Correct
6 Correct 5 ms 268 KB Correct
7 Correct 5 ms 288 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 0 ms 208 KB Correct
10 Correct 1 ms 208 KB Correct
11 Correct 2 ms 208 KB Correct
12 Correct 4 ms 304 KB Correct
13 Correct 3 ms 316 KB Correct
14 Correct 3 ms 304 KB Correct
15 Correct 5 ms 308 KB Correct
16 Correct 3 ms 316 KB Correct
17 Correct 3 ms 304 KB Correct
18 Correct 3 ms 316 KB Correct
19 Correct 3 ms 312 KB Correct
20 Correct 3 ms 312 KB Correct
21 Correct 3 ms 316 KB Correct
22 Correct 0 ms 208 KB Correct
23 Correct 1 ms 288 KB Correct
24 Correct 2 ms 208 KB Correct
25 Correct 3 ms 312 KB Correct
26 Correct 3 ms 312 KB Correct
27 Correct 5 ms 292 KB Correct
28 Correct 3 ms 268 KB Correct