Submission #1206207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206207		thelegendary08	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1095 ms	4024 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);
		*/
		int ans = 4e18;
		vi loc;
		f0r(i, n)loc.pb(i);
		do{
			bool ok = 1;
			for(int i = 0; i<n; i+=2){
				if(s[loc[i]] < 0 && s[loc[i+1]] > 0 && s[loc[i]] == -s[loc[i+1]]){
					
				}
				else ok = 0;
			}
			if(ok){
				os a;
				a.insert(loc[n-1]);
				int cur = 0;
				for(int i = n-2; i>=0; i--){
					cur += a.order_of_key(loc[i]);
					a.insert(loc[i]);
				}
				ans = min(ans, cur);
			}
		}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