Submission #832149

#	Time	Username	Problem	Language	Result	Execution time	Memory
832149		tranxuanbach	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	51 ms	16400 KiB

shoes

#include "shoes.h"

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

#define isz(a) ((signed)a.size())

using ll = long long;

const int N = 2e5 + 5;

int n;
int a[N];

namespace subtask6{
	bool check(){
		return true;
	}

	struct fenwick_tree{
		int fen[N];

		void update(int i, int x){
			for (; i < N; i += i & -i){
				fen[i] += x;
			}
		}

		int query(int i){
			int ans = 0;
			for (; i > 0; i -= i & -i){
				ans += fen[i];
			}
			return ans;
		}

		int query(int l, int r){
			return query(r) - query(l - 1);
		}
	} fen;

	vector <int> pos[N];
	int final_pos[N];

	ll solve(){
		for (int i = 1; i <= 2 * n; i++){
			pos[a[i] + n].emplace_back(i);
		}
		for (int val = 0; val <= 2 * n; val++){
			reverse(pos[val].begin(), pos[val].end());
		}
		int cnt = 0;
		for (int i = 1; i <= 2 * n; i++){
			if (final_pos[i] != 0){
				continue;
			}
			int val1 = a[i], val2 = -a[i];
			int j = pos[val2 + n].back();
			pos[val1 + n].pop_back();
			pos[val2 + n].pop_back();
			final_pos[i] = cnt * 2 + (val1 < 0 ? 1 : 2);
			final_pos[j] = cnt * 2 + (val2 < 0 ? 1 : 2);
			cnt++;
		}
		ll ans = 0;
		for (int i = 1; i <= 2 * n; i++){
			ans += fen.query(final_pos[i] + 1, 2 * n);
			fen.update(final_pos[i], 1);
		}
		return ans;
	}
}

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

	if (subtask6::check()){
		return subtask6::solve();
	}
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

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