Submission #810201

#	Time	Username	Problem	Language	Result	Execution time	Memory
810201		NothingXD	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	60 ms	19172 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

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

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail> 
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, f[maxn];
vector<int> idx[maxn][2];
bool mark[maxn];

void add(int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

int get(int idx){
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

ll count_swaps(vector<int> s) {
	n = s.size();
	for (int i = 0; i < n; i++){
		add(i+1, 1);
		if (s[i] < 0) idx[-s[i]][0].push_back(i);
		else idx[s[i]][1].push_back(i);
		mark[i] = true;
	}
	for (int i = 1; i <= n; i++){
		reverse(all(idx[i][0]));
		reverse(all(idx[i][1]));
	}
	ll ans = 0;
	for (int i = 0; i < n; i++){
		if (!mark[i]) continue;
		mark[i] = false;
		if (s[i] > 0) ans++;
		int ptr = abs(s[i]);
		int ptr2 = (s[i] > 0? 1: 0);
		add(i+1, -1);
		idx[ptr][ptr2].pop_back();
		ans += get(idx[ptr][1-ptr2].back());
		add(idx[ptr][1-ptr2].back()+1, -1);
		mark[idx[ptr][1-ptr2].back()] = false;
		idx[ptr][1-ptr2].pop_back();
	}
	return ans;
}

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