Submission #1207890

#TimeUsernameProblemLanguageResultExecution timeMemory
1207890countlessThe Collection Game (BOI21_swaps)C++20
100 / 100
2 ms428 KiB
// // --- 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. // #include "swaps.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 998244353; const ll INF = 1e18; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define REP(i, a, b) for(ll i = a; i < b; i++) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template <typename Key, typename Value> using hash_map = unordered_map<Key, Value, custom_hash>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // uniform_int_distribution<int>(a, b)(rng); // shuffle(all(a), rng); // concurrent sorts // https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort void solve(int n, int v) { // 60% vector<int> at(n); iota(all(at), 1); vector<pair<int, int>> queries; auto in = [&](int x) -> bool { // return (0 < x and x <= n); return (0 <= x and x < n); }; auto reset = [&]() -> void { queries.clear(); }; auto query = [&](int a, int b) -> void { if (!in(a) or !in(b)) { return; } schedule(at[a], at[b]); queries.push_back({a, b}); }; auto handle = [&]() -> void { vector<int> res = visit(); int m = queries.size(); for (int i = 0; i < m; i++) { auto [a, b] = queries[i]; if (res[i] == 0) { swap(at[a], at[b]); } } }; int pw2 = 1; while (pw2 < n) pw2 *= 2; for (int k = 2; k <= pw2; k *= 2) { for (int j = k; j > 1; j /= 2) { reset(); if (j == k) { for (int i = 0; i < pw2; i++) { int d = i % j; int l = i + j - d - d - 1; if (l > i) query(i, l); } } else { vector<bool> vis(n, false); for (int i = 0; i < pw2; i++) { int l = i + (j / 2); if (l > i and !vis[l] and !vis[i]) { vis[i] = true, vis[l] = true; query(i, l); } } } handle(); } } answer(at); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...