Submission #712975

#	Time	Username	Problem	Language	Result	Execution time	Memory
712975		mseebacher	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	137 ms	54188 KiB

shoes

//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const lld pi = 3.14159265358979323846;



#define MAXI (int)1e5
#define LSOne(S) ((S) & -(S))
#define MSB(S) __builtin_clz(S)
vector<int> ad[MAXI];


 
vector<ll> ft;

ll sumFT(int index){
	ll sum = 0;
	while(index > 0){	
		sum+= ft[index];
		index -= LSOne(index);
	}
	return sum;
}
 
int getval(int index){
	int x = sumFT(index)-sumFT(index-1);
	if(x == 0) return 1; else return -1;
}
 
void updateFT(int index, ll val){
	while(index < (int)ft.size()){
		ft[index] += val;
		index += LSOne(index);
	}
}
 

long long count_swaps(vector<int> a){

	int n = a.size();
	vector<set<int>> left(2*n+1);
	vector<set<int>> right(2*n+1);
	
	vector<bool> marked(2*n,0);
	ll ans = 0;
	for(int i = 1;i<=n;i++){
		if(a[i-1] < 0){
			int x = a[i-1]*-1;
			left[x].insert(i);
		}else right[a[i-1]].insert(i);
	}
	ft.assign(n+1,0);
	for(int i = 1;i<=n;i++){
		updateFT(i,1);
	}
	int links,rechts;
	for(int i = 0;i<n;i++){
		if(marked[i]) continue;
		links = i+1;
		if(a[i] < 0) {
			rechts = *right[abs(a[i])].begin();
			ans--;
		}else{
			rechts = *left[a[i]].begin();
		}
		
		ans += sumFT(rechts)-sumFT(links);
		updateFT(links,-1);
		updateFT(rechts,-1);
		right[abs(a[i])].erase(*right[abs(a[i])].begin());
		left[abs(a[i])].erase(*left[abs(a[i])].begin());
		
		marked[links-1] = 1;
		marked[rechts-1] = 1;
	}
	
	
	return ans;
}

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