Submission #1195578

#TimeUsernameProblemLanguageResultExecution timeMemory
1195578nekolieArranging Shoes (IOI19_shoes)C++20
50 / 100
16 ms6724 KiB
// When she's prettier than any DP you've ever seen... #include <bits/stdc++.h> using namespace std; const int baza = (1<<17); int d[2*baza]; int pierwszy() { int v = 1; while (v < baza) v = ((d[2*v] > 0) ? 2*v : 2*v+1); return v-baza; } void akt(int i) { i = (i+baza)/2; while (i > 0) d[i] = d[2*i]+d[2*i+1], i /= 2; } int suma(int l, int r) { int wynik = 0; l += baza-1, r += baza+1; while (l/2 != r/2) { if (l%2 == 0) wynik += d[l+1]; if (r%2 == 1) wynik += d[r-1]; l /= 2, r /= 2; } return wynik; } long long count_swaps(vector<int> S) { int n = S.size()/2; vector<int> ind[n+1][2]; for (int i = 2*n-1; i >= 0; i--) { d[i+baza] = 1; if (S[i] < 0) ind[-S[i]][0].push_back(i); else ind[S[i]][1].push_back(i); } for (int i = baza-1; i > 0; i--) d[i] = d[2*i]+d[2*i+1]; long long odp = 0; while (d[1] > 0) { int x = pierwszy(), y; if (S[x] > 0) y = ind[S[x]][0].back(), odp++; else y = ind[-S[x]][1].back(); ind[abs(S[x])][0].pop_back(), ind[abs(S[x])][1].pop_back(); d[x+baza] = d[y+baza] = 0, akt(x), akt(y), odp += suma(x,y); } return odp; }
#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...