Submission #1080012

#TimeUsernameProblemLanguageResultExecution timeMemory
1080012juicySorting (IOI15_sorting)C++17
100 / 100
115 ms24660 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; int findSwapPairs(int n, int *s, int m, int *x, int *y, int *p, int *q) { vector<int> a(n), pos(n); vector<array<int, 2>> ops(m); auto count = [&](int k) { for (int i = 0; i < n; ++i) { a[i] = s[i]; } for (int i = 0; i < k; ++i) { swap(a[x[i]], a[y[i]]); } for (int i = 0; i < n; ++i) { pos[a[i]] = i; } int cnt = 0; for (int i = 0; i < n; ++i) { if (i == a[i]) { continue; } int j = pos[i]; ops[cnt++] = {a[i], a[j]}; swap(pos[a[i]], pos[a[j]]); swap(a[i], a[j]); } return cnt; }; int l = 0, r = m, k = m; while (l <= r) { int md = (l + r) / 2; if (count(md) <= md) { k = md; r = md - 1; } else { l = md + 1; } } auto cnt = count(k); for (int i = cnt; i < k; ++i) { ops[i] = {0, 0}; } for (int i = 0; i < n; ++i) { pos[s[i]] = i; } auto swp = [&](int i, int j) { swap(pos[s[i]], pos[s[j]]); swap(s[i], s[j]); }; for (int i = 0; i < k; ++i) { swp(x[i], y[i]); auto [x, y] = ops[i]; tie(p[i], q[i]) = tie(pos[x], pos[y]); swp(p[i], q[i]); } return k; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:55:11: warning: declaration of 'auto x' shadows a parameter [-Wshadow]
   55 |     auto [x, y] = ops[i];
      |           ^
sorting.cpp:7:46: note: shadowed declaration is here
    7 | int findSwapPairs(int n, int *s, int m, int *x, int *y, int *p, int *q) {
      |                                         ~~~~~^
sorting.cpp:55:14: warning: declaration of 'auto y' shadows a parameter [-Wshadow]
   55 |     auto [x, y] = ops[i];
      |              ^
sorting.cpp:7:54: note: shadowed declaration is here
    7 | int findSwapPairs(int n, int *s, int m, int *x, int *y, int *p, int *q) {
      |                                                 ~~~~~^
#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...