Submission #1292187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292187		shidou26	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	190 ms	274168 KiB

shoes

#ifndef KURUMI
	#include "shoes.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#ifdef KURUMI
    #include "algo/debug.h"
#endif

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]" 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
    if(seed == 0) return rand(l, r);
    else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}

template<typename S, typename T> bool maximize(S &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename S, typename T> bool minimize(S &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;

const int N = 2e5 + 3;
const ll INF = 1e18 + 3;

int n;
int a[N];

namespace subtask_1 {
	bool approve() {
		return n == 1;
	}

	ll execute() {
		return (a[1] > a[2]);
	}
}

namespace subtask_2 {
	bool approve() {
		return n <= 8;
	}

	const int N = 12;

	ll answer = INF;
	int order[N];
	deque<int> pos[N], tmp[N];

	int calc() {
		int tot = 0;
		for(int i = 1; i <= 2 * n; i++) {
			for(int j = 1; j < i; j++) {
				tot += (order[j] > order[i]);
			}
		}
		return tot;
	}

	ll execute() {
		vector<int> lab;
		for(int i = 1; i <= 2 * n; i++) {
			if(a[i] > 0) pos[a[i]].push_back(i);
			else lab.push_back(i);
		}

		do {
			for(int i = 1; i <= n; i++) tmp[i] = pos[i];
			for(int i = 1; i <= 2 * n; i += 2) order[i] = lab[(i - 1) / 2];
			for(int i = 2; i <= 2 * n; i += 2) {
				order[i] = tmp[-a[lab[i / 2 - 1]]].front();
				tmp[-a[lab[i / 2 - 1]]].pop_front();
			}
			minimize(answer, calc());
		}while(next_permutation(all(lab)));

		return answer;
	}
}

namespace subtask_6 {
	bool approve() {
		return true;
	}

	struct FenwickTree {
		vector<int> tr;
		FenwickTree (int n) : tr(n + 3) {}

		void update(int p, int v) {
			for(; p > 0; p -= p & -p) 
				tr[p] += v;
		}

		int get(int p) {
			int tot = 0;
			for(; p < sz(tr); p += p & -p) tot += tr[p];
			return tot;
		}
	};

	int last[N];
	bool pushed[N];
	deque<int> big[N], small[N];

	ll execute() {
		vector<int> order;

		// optimal because it does not interfere with any other swap
		for(int i = 2 * n; i >= 1; i--) {
			if(a[i] < 0) {
				a[i] = -a[i];
				if(!big[a[i]].empty()) {
					// cout << i << " " << big[a[i]].front() << endl;
					order.push_back(big[a[i]].front());
					order.push_back(i);
					big[a[i]].pop_front();
				}else small[a[i]].push_back(i);
			}else {
				if(!small[a[i]].empty()) {
					// cout << i << " " << small[a[i]].front() << endl;
					order.push_back(i);
					order.push_back(small[a[i]].front());
					small[a[i]].pop_front();
				}else big[a[i]].push_back(i);
			}
		} 

		ll answer = 0;
		FenwickTree ft(2 * n);

		reverse(all(order));
		for(int p : order) {
			answer += ft.get(p);
			ft.update(p, 1);
		}

		return answer;
	}
}

ll count_swaps(vector<int> s) {
	n = sz(s) / 2;
	for(int i = 1; i <= 2 * n; i++) {
		a[i] = s[i - 1];
	}

	if(subtask_1::approve()) return subtask_1::execute();
	if(subtask_2::approve()) return subtask_2::execute();
	if(subtask_6::approve()) return subtask_6::execute();

	return -1;
}

#ifdef KURUMI
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "Deeto"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    int n; cin >> n;

    vector<int> s(2 * n);
    for(int i = 0; i < 2 * n; i++) cin >> s[i];

    cout << count_swaps(s) << endl;

    cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
    cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
    
    return 0;
}
#endif

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