Submission #368402

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
3684022021-02-20 03:04:35KoDSorting (IOI15_sorting)C++17
100 / 100
725 ms15724 KiB
#include <bits/stdc++.h>
#include "sorting.h"
template <class T>
using Vec = std::vector<T>;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int ok = M, ng = -1;
while (ok - ng > 1) {
int md = (ok + ng) / 2;
Vec<int> perm(N);
Vec<int> inv(N);
std::iota(perm.begin(), perm.end(), 0);
std::iota(inv.begin(), inv.end(), 0);
const auto swap = [&](const int i, const int j) {
std::swap(perm[i], perm[j]);
inv[perm[i]] = i;
inv[perm[j]] = j;
};
for (int i = 0; i < md; ++i) {
swap(X[i], Y[i]);
}
std::queue<std::pair<int, int>> que;
{
Vec<int> to(N);
for (int i = 0; i < N; ++i) {
to[S[i]] = inv[i];
}
Vec<char> used(N);
for (int i = 0; i < N; ++i) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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...