Submission #433061

#TimeUsernameProblemLanguageResultExecution timeMemory
433061timmyfengSorting (IOI15_sorting)C++17
100 / 100
332 ms15192 KiB
#include <bits/stdc++.h> using namespace std; #include "sorting.h" const int N = 200000; int perm[N], inv[N], first[N], second[N]; bool visited[N]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { int low = 0, high = M + 1; while (low < high) { int mid = (low + high) / 2; copy(S, S + N, perm); for (int i = 0; i < mid; ++i) { swap(perm[X[i]], perm[Y[i]]); } int count = 0; fill(visited, visited + N, false); fill(first, first + N, 0); fill(second, second + N, 0); for (int i = 0; i < N; ++i) { while (perm[i] != i) { first[count] = perm[i], second[count] = perm[perm[i]], ++count; swap(perm[i], perm[perm[i]]); } } if (count <= mid) { high = mid; copy(S, S + N, perm); for (int i = 0; i < N; ++i) { inv[perm[i]] = i; } for (int i = 0; i < mid; ++i) { swap(perm[X[i]], perm[Y[i]]); swap(inv[perm[X[i]]], inv[perm[Y[i]]]); P[i] = first[i], Q[i] = second[i]; swap(inv[P[i]], inv[Q[i]]); P[i] = inv[P[i]], Q[i] = inv[Q[i]]; swap(perm[P[i]], perm[Q[i]]); } } else { low = mid + 1; } } return low; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:11:23: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   11 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:6:11: note: shadowed declaration is here
    6 | const int N = 200000;
      |           ^
#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...