Submission #533021

#	Time	Username	Problem	Language	Result	Execution time	Memory
533021		gun_gan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	100 ms	21464 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<int> L[n + 1], R[n + 1];
	for(int i=0;i<n;i++)
	{
		if(s[i] < 0) L[-s[i]].push_back(i);
		else R[s[i]].push_back(i);
	}
	Fenwick<long long> fw(n + 1);
	vector<pair<int,int>> v;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<L[i].size();j++)
		{
			if(L[i][j] > R[i][j])
			{
				ans++;
				swap(L[i][j], R[i][j]);
			}
			v.push_back({L[i][j], R[i][j]});
		}
	}
	sort(v.begin(), v.end());
	for(auto i : v)
	{
		// cout << i.first << " " << i.second << " " << '\n';
		ans += (i.second - i.first - 1) - 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:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j=0;j<L[i].size();j++)
      |               ~^~~~~~~~~~~~
shoes.cpp:29:12: warning: unused variable 'N' [-Wunused-variable]
   29 |  const int N = 1e5 + 1;
      |            ^

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