Submission #1207905

#TimeUsernameProblemLanguageResultExecution timeMemory
1207905jasonicThe Collection Game (BOI21_swaps)C++20
100 / 100
2 ms428 KiB
#include "swaps.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define fastIO cin.tie(0); ios::sync_with_stdio(false) #define cerr if(0) cout vector<int> a; vector<pair<int, int>> visits; vector<int> idx; vector<int> whereis; int n; int calls = 0; void interact(int i, int j) { if(i >= n || j >= n) return; schedule(idx[i]+1, idx[j]+1); visits.push_back({idx[i], idx[j]}); calls++; } void visitFix() { vector<int> a = visit(); for(int i = 0; i < calls; i++) { if(a[i] == 0) { swap(idx[whereis[visits[i].first]], idx[whereis[visits[i].second]]); swap(whereis[visits[i].first], whereis[visits[i].second]); } } calls = 0; visits = vector<pair<int, int>>(); cerr << "\n\n"; for(auto &i : idx) cerr << i << ' '; cerr << "\n\n"; } int lg2(int n) { int res = 0; while(n != 1) {n>>=1; res++;} return res; } void fix(int sz) { for(int i = 1; i < sz; i <<= 1) { // block size // across for(int j = 0; j*i*2 < n; j += 1) { for(int k = 0; k < i && k + j*i*2 < n; k++) { interact(j*i*2 + i - k - 1, k + j*i*2 + i); } } visitFix(); if(i != 1) for(int j = i/2; j > 0; j >>= 1) { for(int k = 0; k*j*2 < n; k++) { for(int l = 0; l < j && l + k*j*2 < n; l++) { interact(k*j*2 + l, k*j*2 + l + j); } } visitFix(); } } } void solve(int N, int v) { n = N; int betN = 1<<lg2(n); if(betN < n) betN *= 2; for(int i = 0; i < n; i++) idx.push_back(i); for(int i = 0; i < n; i++) whereis.push_back(i); a = vector<int>(n); fix(betN); for(int i = 0; i < n; i++) a[i] = idx[i]+1; answer(a); }
#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...