Submission #1206211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206211		thelegendary08	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1096 ms	20712 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';
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
		vout(loc);
		*/
		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);
		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 a;
					a.insert(locc[n-1]);
					int cur = 0;
					for(int i = n-2; i>=0; i--){
						cur += a.order_of_key(locc[i]);
						a.insert(locc[i]);
					}
					ans = min(ans, cur);
				}
			}while(next_permutation(loc2.begin(), loc2.end()));
			
		}while(next_permutation(loc.begin(), loc.end()));
		
		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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15