Submission #944806

#	Time	Username	Problem	Language	Result	Execution time	Memory
944806		PenguinsAreCute	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	68 ms	16656 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct ft {
	vector<int> v; int n;
	ft(int _n): n(_n) {v.resize(n+1,0);}
	inline int lsb(int x) {return x&(-x);}
	void up(int x, int u) {
		for(;x<=n;x+=lsb(x)) v[x]+=u;
	}
	int qry(int x) {
		ll ans = 0;
		for(;x;x-=lsb(x)) ans += v[x];
		return ans;
	}
};
long long count_swaps(std::vector<int> s) {
	int n = s.size() / 2;
	vector<int> v, posP[n+1], posN[n+1];
	for(int i=0;i<2*n;i++) {
		if(s[i]<0) posN[-s[i]].push_back(i);
		else posP[s[i]].push_back(i);
	}
	vector<pair<int,int>> vec;
	for(int i=1;i<=n;i++) for(int j=0;j<posN[i].size();j++) vec.push_back({posN[i][j],posP[i][j]});
	sort(vec.begin(),vec.end(),[](pair<int,int> a, pair<int,int> b) {return a.first+a.second<b.first+b.second;});
	v.resize(2*n);
	for(int i=0;i<2*n;i+=2) {
		v[i] = vec[i>>1].first;
		v[i+1] = vec[i>>1].second;
	}
	ll ans = 0; ft fenwick(2*n);
	for(int i=2*n;i--;) {
		ans += fenwick.qry(v[i]);
		fenwick.up(v[i]+1,1);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:26:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=1;i<=n;i++) for(int j=0;j<posN[i].size();j++) vec.push_back({posN[i][j],posP[i][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