oj.uz

Submission #444656

# Submission time Handle Problem Language Result Execution time Memory
444656 2021-07-14T14:11:33 Z Hegdahl The Collection Game (BOI21_swaps) C++17
85 / 100
 169 ms 1056 KB 
#include "swaps.h"
#include <bits/stdc++.h>

#define ar array

using namespace std;
//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<ar<int, 2>> lvls[5000];

int solve_range(int l, int r) {
  int mid = l + (r-l+1)/2;

  int lvl = 0;

  if (l != mid-1) lvl = max(lvl, solve_range(l, mid-1));
  if (r != mid) lvl = max(lvl, solve_range(mid, r));

  cerr << l << ' ' << r << '\n';

  int gap = r-l+1;
  do {
    gap = (gap+1)/2;
    cerr << gap << '\n';

    set<ar<int, 2>> need;
    for (int i = l, j = l+gap; j <= r; ++i, ++j)
      need.insert({i, j});

    while (need.size()) {
      set<int> taken;
      for (auto it = need.begin(); it != need.end();) {
        auto [i, j] = *it;
        if (taken.count(i) || taken.count(j)) {
          ++it;
          continue;
        }
        else {
          lvls[lvl].push_back({i, j});
          taken.insert(i);
          taken.insert(j);
          need.erase(it++);
        }
      }
      ++lvl;
    }
  } while (gap > 1);

  return lvl+1;
}

void solve(int n, int v) {
  vector<int> a(n);
  iota(a.begin(), a.end(), 0);

  int v_needed = solve_range(0, n-1);
  cerr << "used, allowed: "<< v_needed << ' ' << v << '\n';

  for (int lvl = 0; lvl < v_needed; ++lvl) {
    //*
    for (auto [i, j] : lvls[lvl])
      cerr << '(' << i << ' ' << j << ") ";
    cerr << '\n'; // */
    //*
    vector<ar<int, 2>> scheduled;
    for (auto [i, j] : lvls[lvl]) {
      scheduled.push_back({i, j});
      schedule(a[i]+1, a[j]+1);
    }

    auto res = visit();
    for (int I = 0; I < (int)scheduled.size(); ++I) {
      auto [i, j] = scheduled[I];
      if (!res[I]) swap(a[i], a[j]);
    }
  }

  /*
  vector<int> inv(n);
  for (int i = 0; i < n; ++i)
    inv[a[i]] = i+1;*/

  for (int &x : a) ++x;
  answer(a);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Correct
2 Correct 21 ms 460 KB Correct
3 Correct 65 ms 660 KB Correct
4 Correct 164 ms 872 KB Correct
5 Correct 163 ms 792 KB Correct
6 Correct 163 ms 764 KB Correct
7 Correct 163 ms 1000 KB Correct
8 Correct 169 ms 744 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Correct
2 Correct 20 ms 464 KB Correct
3 Correct 66 ms 556 KB Correct
4 Correct 158 ms 788 KB Correct
5 Correct 164 ms 744 KB Correct
6 Correct 160 ms 760 KB Correct
7 Correct 162 ms 788 KB Correct
8 Correct 161 ms 836 KB Correct
9 Correct 162 ms 780 KB Correct
10 Correct 163 ms 880 KB Correct
11 Correct 165 ms 864 KB Correct
12 Correct 164 ms 752 KB Correct
13 Correct 161 ms 744 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 20 ms 456 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 20 ms 456 KB Correct
3 Correct 1 ms 328 KB Correct
4 Correct 21 ms 456 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Correct
2 Correct 20 ms 456 KB Correct
3 Correct 68 ms 552 KB Correct
4 Correct 164 ms 792 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Correct
2 Correct 20 ms 456 KB Correct
3 Correct 68 ms 552 KB Correct
4 Correct 164 ms 792 KB Correct
5 Correct 2 ms 328 KB Correct
6 Correct 21 ms 456 KB Correct
7 Correct 68 ms 456 KB Correct
8 Correct 165 ms 764 KB Correct
9 Correct 168 ms 984 KB Correct
10 Correct 164 ms 748 KB Correct
11 Correct 161 ms 740 KB Correct
12 Correct 161 ms 884 KB Correct
13 Correct 1 ms 328 KB Correct
14 Correct 21 ms 456 KB Correct
15 Correct 67 ms 456 KB Correct
16 Correct 165 ms 852 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 21 ms 456 KB Correct
3 Correct 65 ms 492 KB Correct
4 Correct 167 ms 784 KB Correct
5 Correct 165 ms 792 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 21 ms 456 KB Correct
3 Correct 65 ms 492 KB Correct
4 Correct 167 ms 784 KB Correct
5 Correct 165 ms 792 KB Correct
6 Correct 2 ms 328 KB Correct
7 Correct 21 ms 456 KB Correct
8 Correct 64 ms 640 KB Correct
9 Correct 164 ms 772 KB Correct
10 Correct 162 ms 796 KB Correct
11 Correct 162 ms 840 KB Correct
12 Correct 165 ms 856 KB Correct
13 Correct 163 ms 872 KB Correct
14 Correct 164 ms 880 KB Correct
15 Correct 162 ms 792 KB Correct
16 Correct 162 ms 764 KB Correct
17 Correct 164 ms 860 KB Correct
18 Correct 158 ms 788 KB Correct
19 Correct 2 ms 328 KB Correct
20 Correct 22 ms 464 KB Correct
21 Correct 68 ms 456 KB Correct
22 Correct 162 ms 760 KB Correct
23 Correct 162 ms 788 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 328 KB Correct
2 Correct 20 ms 456 KB Correct
3 Correct 64 ms 520 KB Correct
4 Correct 161 ms 784 KB Correct
5 Correct 164 ms 788 KB Correct
6 Correct 162 ms 996 KB Correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 328 KB Correct
2 Correct 20 ms 456 KB Correct
3 Correct 64 ms 520 KB Correct
4 Correct 161 ms 784 KB Correct
5 Correct 164 ms 788 KB Correct
6 Correct 162 ms 996 KB Correct
7 Correct 2 ms 328 KB Correct
8 Correct 20 ms 428 KB Correct
9 Correct 64 ms 512 KB Correct
10 Correct 165 ms 768 KB Correct
11 Correct 163 ms 776 KB Correct
12 Correct 163 ms 764 KB Correct
13 Correct 162 ms 868 KB Correct
14 Correct 162 ms 880 KB Correct
15 Correct 163 ms 1028 KB Correct
16 Correct 161 ms 760 KB Correct
17 Correct 162 ms 780 KB Correct
18 Correct 163 ms 760 KB Correct
19 Correct 160 ms 764 KB Correct
20 Correct 1 ms 328 KB Correct
21 Correct 20 ms 456 KB Correct
22 Correct 64 ms 576 KB Correct
23 Correct 164 ms 824 KB Correct
24 Correct 160 ms 744 KB Correct
25 Correct 167 ms 764 KB Correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Correct
2 Correct 20 ms 460 KB Correct
3 Correct 65 ms 524 KB Correct
4 Correct 161 ms 880 KB Correct
5 Correct 169 ms 764 KB Correct
6 Correct 163 ms 764 KB Correct
7 Runtime error 94 ms 1056 KB Execution killed with signal 11

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Correct
2 Correct 20 ms 460 KB Correct
3 Correct 65 ms 524 KB Correct
4 Correct 161 ms 880 KB Correct
5 Correct 169 ms 764 KB Correct
6 Correct 163 ms 764 KB Correct
7 Runtime error 94 ms 1056 KB Execution killed with signal 11