Submission #1206204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206204		thelegendary08	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	330 ms	33292 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
int count_swaps(std::vector<signed> s) {
	int n = s.size();
	if(n == 2){
		if(s[0] < 0)return 0;
		else return 1;
	}
	else{
		vi rs;
		vi loc(n);
		int cur = 0;
		map<int,vi> m;
		f0r(i,n){
			if(s[i] < 0){
				loc[i] = cur;
				m[-s[i]].pb(cur+1);
				cur += 2;
			}
		}
		map<int,int>ptr;
		for(auto u : m){
			ptr[u.first] = 0;
		}
		f0r(i, n){
			if(s[i] > 0){
				loc[i] = m[s[i]][ptr[s[i]]];
				ptr[s[i]]++;
			}
		}
		//how many ppl after me are less than me
		os a;
		a.insert(loc[n-1]);
		int ans = 0;
		for(int i = n-2; i>=0; i--){
			ans += a.order_of_key(loc[i]);
			a.insert(loc[i]);
		}
		
		return ans;
		
		/*
		vi tar;
		for(int i = 1; i<n; i+=2){
			tar.pb(i);
		}
		int ans = 0;
		f0r(i, rs.size()){
			ans += abs(rs[i] - tar[i]);
		}
		return ans;
		*/
	}
	return 1;
}

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