Submission #1215847

#TimeUsernameProblemLanguageResultExecution timeMemory
1215847ZsofiaKeresztelyArranging Shoes (IOI19_shoes)C++20
30 / 100
1096 ms3516 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll count_swaps(vector<int> s) { ll n = s.size() / 2; vector<ll> p; for (int i=0; i<2*n; i++){ if (s[i] > 0){ p.push_back(s[i]); } } sort(p.begin(), p.end()); ll op = 1e9, inv; //1e9!! do{ inv = 0; vector<int> sc(2*n, 0); for (int i=0; i<n; i++){ sc[2*i] = -p[i]; sc[2*i+1] = p[i]; } for (ll i=0; i<2*n; i++){ ll j = i; //cout << sc[j] << " " << s[i] << "\n"; while (sc[j] != s[i]){ j++; } inv += j - i; while (j > i){ swap(sc[j], sc[j-1]); j--; } } op = min(op, inv); //cout << 2 << endl; } while (next_permutation(p.begin(), p.end())); return op; }
#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...