답안 #444656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444656	2021-07-14T14:11:33 Z	Hegdahl	The Collection Game (BOI21_swaps)	C++17	85 / 100	169 ms	1056 KB

swaps

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	328 KB	Correct
2	Correct	20 ms	456 KB	Correct

Subtask #4
2.0 / 2.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #444656

Compilation message