Submission #490768

#	Time	Username	Problem	Language	Result	Execution time	Memory
490768		hoangtung_pro	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	242 ms	274344 KiB

shoes

#include<bits/stdc++.h>
 
#define bit(s, i) (s & (1<<i))
#define fi first
#define se second
#define pb push_back
#define endl '\n'
 
using namespace std;
 
const int N = 2e5 + 5;
const int M = 1;
const int K = 1;
const int inf = 2e9;
const long long Inf = 2e18;
const int mod = 1e9 + 7;
 
typedef pair < int, int > ii;
typedef long long ll;
 
int Bit[N], cur[N];
queue < int > pos[N][2];
 
void Update(int i) {
	for(; i < N; i += (i & -i)) Bit[i] ++; 
}
 
int Get(int i) {
	int res = 0;
	for(; i > 0; i -= (i & -i)) res += Bit[i];
	return res;
}
 
long long count_swaps(vector<int> a) {
	int n = a.size() / 2;
	vector < int > solve;
	for(int i=0;i<=2 * n - 1;++i) {
		int x = a[i];
		
		if(x < 0) {
			if(cur[abs(x)] <= 0) solve.pb(abs(x));
			pos[abs(x)][0].push(i + 1);
			cur[abs(x)] --;
			
		}
		else {
			if(cur[abs(x)] >= 0) solve.pb(abs(x));
			pos[abs(x)][1].push(i + 1);
			cur[abs(x)] ++;
		}


	}
	long long res = 0;
	int cnt = 0;
 
	for(int x : solve) {
		int le = pos[x][0].front(), ri = pos[x][1].front();
		pos[x][0].pop(), pos[x][1].pop();
 
		if(le > ri) {
			res ++;
			swap(le, ri);
		}
		//cout << cnt << ' ' << cnt2 << endl;
		res += le + ri;
		res -= 2 * (cnt + 2) - 1;
 
		res -= Get(le) - cnt;
		Update(le), cnt ++;
		res -= Get(ri) - cnt;
		Update(ri), cnt ++;
	}	
 
	return res;
}
 
// int main() {
// 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// 	freopen("trash.inp", "r", stdin);
// 	freopen("trash.out", "w", stdout);
 
// 	int t;
// 	cin >> t;
// 	vector < int > a;
// 	for(int i=1;i<=2*t;++i) {
// 		int x;
// 		cin >> x;
// 		a.pb(x);
// 	}
// 	cout << count_swaps(a);
// }

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