Submission #1047323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047323		efedmrlr	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	41 ms	14560 KiB

shoes

#include "shoes.h"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;

struct Fenwick {
	vector<int> data;
	int n;
	void reset(int s) {
		n = s;
		data.assign(n + 3, 0);
	}
	void update(int ind, int val) {
		ind++;
		while(ind <= n) {
			data[ind] += val;
			ind += ind & (-ind);
		}
	}
	int getSum(int ind) {
		ind++;
		int ret = 0;
		while(ind > 0) {
			ret += data[ind];
			ind -= ind & (-ind);
		}
		return ret;
	}
	int query(int l, int r) {

		return getSum(r) - (l > 0 ? getSum(l - 1) : 0);
	}
};

long long count_swaps(std::vector<int> s) {
	int n = (int)s.size() / 2;
	vector<vector<int> > sn(n + 2, vector<int>()), sp(n + 2, vector<int>());
	vector<array<int, 2> > pr;
	for(int i = 0; i < 2*n; i++) {
		if(s[i] < 0) {
			sn[abs(s[i])].pb(i);
		}
		else {
			sp[abs(s[i])].pb(i);
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < sn[i].size(); j++) {
			pr.pb({sn[i][j], sp[i][j]});
			
		}
	}
	sort(all(pr), [&](array<int, 2> x, array<int, 2> y) {
		return x[0] + x[1] < y[0] + y[1];
	});
	Fenwick fn;
	fn.reset(2*n + 3);
	int ans = 0;
	int cur = 0;
	for(int i = 0; i < n; i++) {
		for(auto c : pr[i]) {
			s[cur] = c;
			cur++;
		}
	}
	for(int i = 0; i < 2*n; i++) {
		// cout << "i:" << s[i] << "\n";
		ans += fn.query(s[i] + 1, 2*n);
		fn.update(s[i], 1);
	}

	return ans;

}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int j = 0; j < sn[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~

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