Submission #302595

#	Time	Username	Problem	Language	Result	Execution time	Memory
302595		AmineTrabelsi	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	88 ms	10480 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ff first
#define ss second
#define em emplace_back 
#define mp make_pair
typedef pair<int,int> ii;
const int M = 1e5 + 10;
int tree[M*2];
int x;
void add(int k,int n){
	while(k <= x){
		tree[k] += n;
		k += k& - k;
	}
}
int sum(int i){
	int res = 0;
	while(i >= 1){
		res += tree[i];
		i -= i& - i;
	}
	return res;
}
vector<ii> ord[M];
ll count_swaps(vector<int> s){
	ll res = 0;
	x = s.size();
	int n = x/2;
	for(int i=0;i<x;i++){
		ord[abs(s[i])].em(mp(s[i],i));
	}
	vector<ii> v;
	for(int i=1;i<=n;i++){
		sort(ord[i].begin(),ord[i].end());
		for(int j=0;j<ord[i].size()/2;j++){
			int f = ord[i][j].second,
			s = ord[i][j+(ord[i].size()/2)].second;
			if(f > s){
				swap(f,s);
				res++;
			}
			v.em(mp(f+1,s+1));
		}
	}
	//cout << res << endl;
	sort(v.begin(),v.end());
	//for(auto i:v)cout << i.ff << " " << i.ss << endl;
	for(int i=1;i<=n*2;i++)add(i,1);
	for(auto i:v){
		res += sum(i.ss-1)-sum(i.ff);
		add(i.ss,-1);
		add(i.ff,-1);
	}
	return res;
}
/*
int main(){return 0;}*/

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int j=0;j<ord[i].size()/2;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