Submission #135244

#TimeUsernameProblemLanguageResultExecution timeMemory
135244JustasZSorting (IOI15_sorting)C++14
20 / 100
3 ms504 KiB
#include "sorting.h" #include <bits/stdc++.h> #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) (int)a.size() #define x first #define y second #define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n" #define rd() abs((int)rng()) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int>pii; const int maxn = 2e5 + 100; const int mod = 1e9 + 7; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); int findSwapPairs(int n, int arr[], int m, int X[], int Y[], int P[], int Q[]) { auto chk = [&](int val, bool f = false) -> bool { vector<int>finalpos(n, 0), cur(n, 0); for(int i = 0; i < n; i++) cur[i] = i; for(int i = 0; i < val; i++) swap(cur[X[i]], cur[Y[i]]); for(int i = 0; i < n; i++) finalpos[cur[i]] = i; vector<int>where(n), v(n); for(int i = 0; i < n; i++) { v[i] = arr[i]; where[v[i]] = i; } int sw = 0; for(int i = 0; i < n; i++) { if(finalpos[i] != v[i]) { if(sw >= val) return false; int pos = where[finalpos[i]]; swap(v[pos], v[i]); P[sw] = pos, Q[sw] = i; swap(where[v[i]], where[v[pos]]); swap(finalpos[X[sw]], finalpos[Y[sw]]); swap(v[X[sw]], v[Y[sw]]); swap(where[v[X[sw]]], where[v[Y[sw]]]); ++sw; --i; } } while(sw < m) { P[sw] = Q[sw] = 0; ++sw; } return true; }; int l = 0, r = m; while(l < r) { int mid = (l + r) / 2; if(chk(mid)) r = mid; else l = mid + 1; } chk(l); return l; }

Compilation message (stderr)

sorting.cpp: In lambda function:
sorting.cpp:19:35: warning: unused parameter 'f' [-Wunused-parameter]
  auto chk = [&](int val, bool f = false) -> bool
                                   ^~~~~
#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...