Submission #671782

#	Time	Username	Problem	Language	Result	Execution time	Memory
671782		mseebacher	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1087 ms	16636 KiB

shoes

#include<bits/stdc++.h>
typedef long long ll;
 
using namespace std;
long long int count_swaps(vector<int> s){
  	int n = s.size();
  	vector<int> pos(n,0);
    vector<set<int>> schuhe(n+1);
		 for(int i = 0;i<n;i++) {
			if(s[i] > 0){
				schuhe[s[i]].insert(i);
			}
		}
		ll val = 0;
		for(int i = 0;i<n;i++){
			if(s[i] < 0){
				int index = *schuhe[-s[i]].begin();
				if(index == i+1){
					schuhe[-s[i]].erase(index);
					continue;
				}
				if(index == i-1){
					schuhe[-s[i]].erase(index);
					val++;
					continue;
				}
				if(i > index){
					val = val + abs(index-i)-(pos[i]-pos[index]);
					for(int j = 0;j<index;j++) pos[j]++;
				}else{
					val = val + index-i-1-(pos[index]-pos[i]);
					for(int j = index+1;j<n;j++) pos[j]++;
				}
				schuhe[-s[i]].erase(index);
			}
			
		}
  return val;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15