제출 #1290915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290915		gustavo_d	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	34 ms	13740 KiB

shoes

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

#define sz(v) (int)(v).size()

typedef long long ll;

const int MAXN = 1e5;

int p[2*MAXN];
vector<int> pos[MAXN+1][2];

struct BIT {
	vector<int> bit; int n;

	BIT(int _n=0): bit(_n+11, 0), n(_n+10) {}

	void update(int i, int v) {
		i+=5;
		while (i <= n) {
			bit[i] += v;
			i += (i & -i);
		}
	}

	int sum(int i) {
		i+=5;
		int res = 0;
		while (i > 0) {
			res += bit[i];
			i -= (i & -i);
		}
		return res;
	}
};

ll count_swaps(vector<int> arr) {
	int n = sz(arr) / 2;

	// cout << n << endl;
	
	for (int i=0; i<2*n; i++) {
		// cout << i << endl;
		pos[abs(arr[i])][arr[i] > 0].push_back(i);
		p[i] = -1;
	}
	for (int i=1; i<=2*n; i++) 
		for (int f=0; f<2; f++) reverse(pos[i][f].begin(), pos[i][f].end());

	for (int i=0, pt=0; i<2*n; i++) {
		if (p[i] != -1) continue;
		// cout << pt << ':' << pos[abs(arr[i])][0].back() << ' ' << pos[abs(arr[i])][1].back() << endl;
		p[pos[abs(arr[i])][0].back()] = pt;
		p[pos[abs(arr[i])][1].back()] = pt+1;
		pos[abs(arr[i])][0].pop_back();
		pos[abs(arr[i])][1].pop_back();
		pt+=2;
	}

	// for (int i=0; i<2*n; i++) cout << p[i] << ' ';
	// cout << endl;

	BIT bit(2*n); ll ans = 0;
	for (int i=2*n-1; i>=0; i--) {
		ans += bit.sum(p[i]);
		bit.update(p[i], 1);
	}

	return ans;
}

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