oj.uz

Submission #444655

# Submission time Handle Problem Language Result Execution time Memory
444655 2021-07-14T14:10:36 Z Hegdahl The Collection Game (BOI21_swaps) C++17
42 / 100
 191 ms 1052 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;

  answer(inv);
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 328 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 23 ms 428 KB Correct

Subtask #4
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 23 ms 428 KB Correct
3 Incorrect 2 ms 328 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 22 ms 456 KB Correct
3 Correct 65 ms 512 KB Correct
4 Correct 169 ms 796 KB Correct

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 22 ms 456 KB Correct
3 Correct 65 ms 512 KB Correct
4 Correct 169 ms 796 KB Correct
5 Incorrect 2 ms 328 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 30 ms 468 KB Correct
3 Correct 67 ms 508 KB Correct
4 Correct 191 ms 780 KB Correct
5 Correct 162 ms 748 KB Correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 30 ms 468 KB Correct
3 Correct 67 ms 508 KB Correct
4 Correct 191 ms 780 KB Correct
5 Correct 162 ms 748 KB Correct
6 Incorrect 2 ms 328 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 21 ms 468 KB Correct
3 Correct 67 ms 456 KB Correct
4 Correct 163 ms 852 KB Correct
5 Correct 163 ms 804 KB Correct
6 Correct 168 ms 764 KB Correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Correct
2 Correct 21 ms 468 KB Correct
3 Correct 67 ms 456 KB Correct
4 Correct 163 ms 852 KB Correct
5 Correct 163 ms 804 KB Correct
6 Correct 168 ms 764 KB Correct
7 Incorrect 2 ms 328 KB Not correct
8 Halted 0 ms 0 KB -

Subtask #11
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 65 ms 532 KB Correct
4 Correct 173 ms 752 KB Correct
5 Correct 182 ms 812 KB Correct
6 Correct 175 ms 780 KB Correct
7 Runtime error 98 ms 1052 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 456 KB Correct
3 Correct 65 ms 532 KB Correct
4 Correct 173 ms 752 KB Correct
5 Correct 182 ms 812 KB Correct
6 Correct 175 ms 780 KB Correct
7 Runtime error 98 ms 1052 KB Execution killed with signal 11