Submission #533017

#	Time	Username	Problem	Language	Result	Execution time	Memory
533017		gun_gan	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	46 ms	14656 KiB

shoes

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

template <typename T>
struct Fenwick {
    vector<T> t;
    T n;
    Fenwick(T n) : n(n) {
        t.resize(n);
    }
    T g(T r){
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += t[r];
        return ret;
    }
    T sum(T l, T r){
        return g(r) - g(l - 1);
    }
    void add(T i, T v){
        for(;i < n; i = i | (i + 1))
            t[i] += v;
    }
};


long long count_swaps(vector<int> s){
	long long n = s.size(), ans = 0;
	const int N = 1e5 + 1;
	vector<pair<int,int>> p[N];
	for(int i=0;i<n;i++)
	{
		p[abs(s[i])].push_back({s[i], i + 1});
	}
	for(int i=1;i<=n;i++)
	{
		sort(p[i].begin(), p[i].end());
	}
	Fenwick<long long> fw(n + 100);
	for(int i=1;i<=n;i++) fw.add(i, 1);
	vector<pair<int,int>> v;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<p[i].size()/2;j++)
		{
			int l = p[i][j].second;
			int r = p[i][j + int(p[i].size())/2].second;
			if(l > r)
			{
				ans++;
				swap(l, r);
			}	
			v.push_back({l, r});
		}
	}
	sort(v.begin(), v.end());
	for(auto i : v)
	{
		ans += fw.sum(i.first + 1, i.second - 1);
		fw.add(i.second, -1);
		fw.add(i.first, -1);
	}
	return ans;
}


// signed main(){
// 	int n;
// 	cin >> n;
// 	vector<int> t(2*n);
// 	for(int i=0;i<2*n;i++) cin >> t[i];
// 	cout << count_swaps(t) << '\n';
// }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:44: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]
   44 |   for(int j=0;j<p[i].size()/2;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