Submission #159187

#TimeUsernameProblemLanguageResultExecution timeMemory
159187BilyanaArranging Shoes (IOI19_shoes)C++17
50 / 100
1083 ms140536 KiB
#include<iostream> #include<queue> #include<cmath> using namespace std; const int MAXN = 200000; int n, to[MAXN+10]; queue<int> bs[MAXN+10]; long long counter=0; /*void input() { int temp; cin>>n; for (int i=0; i<2*n; i++) { cin>>temp; s.push_back(temp); } }*/ void output() { cout<<counter<<endl; } void find_place(vector<int> S) { int curr = 0; int temp; for (int i=0; i<n; i++) { temp = abs(S[i]); if (S[i]>0) { if (!bs[temp].empty() && bs[temp].front()%2==0) { //cout<<i<<' '<<bs[temp].front()<<endl; to[i] = bs[temp].front()+1; bs[temp].pop(); } else { to[i] = curr+1; bs[temp].push(curr+1); curr += 2; } } else { if (!bs[temp].empty() && bs[temp].front()%2==1) { to[i] = bs[temp].front()-1; bs[temp].pop(); } else { to[i] = curr; bs[temp].push(curr); curr += 2; } } } } void sorting() { for (int i=0; i<n; i++) { int nd=i; while (to[nd]!=i && nd<n) nd++; //cout<<i<<" - "; while (nd!=i) { //cout<<nd<<' '; swap(to[nd], to[nd-1]); counter++; nd--; } //cout<<endl; } } void solve(vector<int> S) { n = S.size(); find_place(S); sorting(); } long long count_swaps(vector<int> S) { solve(S); return counter; } /*int main() { ios::sync_with_stdio(false); cin.tie(NULL); input(); solve(); output(); return 0; }*/ /* 3 -2 2 2 -2 -2 2 */
#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...