Submission #143839

#	Time	Username	Problem	Language	Result	Execution time	Memory
143839		sasa	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	129 ms	21232 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
using namespace std;
//#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0)
const int maxn = 2e5 + 10;
vi lef[maxn], rig[maxn];
int a[maxn], b[maxn], fen[maxn];
void add(int p,int val){
	for(p++; p<maxn; p+=p&-p)
		fen[p] += val;
}
int get(int p){
	int res = 0;
	for(; p; p-=p&-p)
		res += fen[p];
	return res;
}
long long count_swaps(vi s) {
	int n = s.size() / 2;
	for(int i=0; i<2*n; i++)
		a[i] = s[i];
	
	for(int i=0; i<2*n; i++){
		int sz = abs(a[i]);
		if(a[i] < 0)
			lef[sz].push_back(i);
		else
			rig[sz].push_back(i);
	}
	vector<pair<int,pii> > tot;
	for(int i=1; i<=n; i++){
		for(int j=0; j<lef[i].size(); j++){
			tot.push_back({ lef[i][j] + rig[i][j], {i, j} });
		}
	}
	sort(all(tot));
	ll ans = 0;
	int cur = 0;
	for(auto t : tot){
		int i = t.Y.X;
		int j = t.Y.Y;
		int l = lef[i][j], r = rig[i][j];
		b[l] = cur;
		b[r] = cur + 1;
		cur += 2;
	}
	for(int i=2*n-1; i>=0; i--){
		int x = b[i];
		ans += get(x);
		add(x, 1);
	}
	return ans;
}/*
int main(){
	int n;
	cin >> n;
	vi s;
	for(int i=0; i<2*n; i++){
		int x;
		cin >> x;
		s.push_back(x);
	}
	cout << count_swaps(s) << endl;
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(vi)':
shoes.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<lef[i].size(); j++){
                ~^~~~~~~~~~~~~~

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