Submission #1206265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206265		thelegendary08	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	125 ms	34832 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>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define dout(x) cout<<x<<' '<<#x<<'\n';
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 a;
		vi b;
		vi c; vi d;
		f0r(i, n){
			if(s[i] < 0){
				a.pb(s[i]);
				c.pb(i);
			}
			else{
				b.pb(s[i]);
				d.pb(i);
			}
		}
		int ans = 4e18;
		vi loc;
		f0r(i, n/2)loc.pb(i);
		vector<vi> opti;
		do{
			vi loc2;
			f0r(i, n/2)loc2.pb(i);
			do{
				bool ok = 1;
				for(int i = 0; i<n/2; i++){
					if(a[loc[i]] != -b[loc2[i]]){
						ok = 0;
					}
				}
				if(ok){
					vi locc;
					f0r(i, n/2){
						locc.pb(c[loc[i]]);
						locc.pb(d[loc2[i]]);
					}
					os ay;
					ay.insert(locc[n-1]);
					int cur = 0;
					for(int i = n-2; i>=0; i--){
						cur += ay.order_of_key(locc[i]);
						ay.insert(locc[i]);
					}
					if(cur < ans){
						ans = cur;
						vi thing;
						f0r(i, n/2){
							thing.pb(-a[loc[i]]);
						}
						opti = {thing};
					}
					else if(cur == ans){
						ans = cur;
						vi thing;
						f0r(i, n/2){
							thing.pb(-a[loc[i]]);
						}
						opti.pb(thing);
					}
				}
			}while(next_permutation(loc2.begin(), loc2.end()));
			
		}while(next_permutation(loc.begin(), loc.end()));
		dout(ans);
		for(auto u : opti){
			vout(u);
		}
		
		
		int a1 = ans;
		*/
		vi rs;
		vi lok(n);
		vector<set<int>> lef(n + 1);
		vector<set<int>>rig(n + 1);
		int cur = 0;
		f0r(i, n){
			if(s[i] > 0){
				if(lef[s[i]].size() > 0){
					lok[(*lef[s[i]].begin())] = cur;
					lef[s[i]].erase(lef[s[i]].begin());
					lok[i] = cur + 1;
					cur += 2;
				}
				else{
					rig[s[i]].insert(i);
				}
			}
			else{
				if(rig[-s[i]].size() > 0){
					lok[(*rig[-s[i]].begin())] = cur + 1;
					rig[-s[i]].erase(rig[-s[i]].begin());
					lok[i] = cur;
					cur += 2;
				}
				else{
					lef[-s[i]].insert(i);
				}
			}
		}
		//how many ppl after me are less than me
		// vout(lok);
		os aa;
		aa.insert(lok[n-1]);
		int ans = 0;
		for(int i = n-2; i>=0; i--){
			ans += aa.order_of_key(lok[i]);
			aa.insert(lok[i]);
		}
		/*
		dout(ans);
		int a2 = ans;
		if(a1 != a2){
			vout(s);
		}
		*/
		
		return ans;
		
	}
	return 1;
}

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