Submission #613991

#	Time	Username	Problem	Language	Result	Execution time	Memory
613991		AlperenT	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1080 ms	46976 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

const int N = 2e5 + 5;

int n;

struct Fenwick{
	int tree[N];

	int getsum(int r){
		int sum = 0;
		for(int i = r; i > 0; i -= i & -i) sum += tree[i];
		return sum;
	}

	int query(int l, int r){
		return getsum(r) - getsum(l - 1);
	}

	void update(int pos, int val){
		for(int i = pos; i < N; i += i & -i) tree[i] += val;
	}
};

Fenwick fw;

int findcnt(vector<int> a, vector<int> b){
    map<int, vector<int>> nums;

    for(int i = 0; i < n; i++) nums[b[i]].push_back(i + 1);

    for(int i = 0; i < n; i++){
        int x = *nums[a[i]].begin(); nums[a[i]].erase(nums[a[i]].begin());
        a[i] = x;
    }

    long long inv = 0;

   	for(auto x : a){
   		inv += fw.query(x + 1, N - 1);
   		fw.update(x, 1);
   	}

    return inv;
}

long long count_swaps(vector<int> arr){
	n = arr.size();

	vector<bool> flag(n, false);

	map<int, vector<int>> mp;

	for(int i = 0; i < n; i++){
		if(mp[-arr[i]].empty()) mp[arr[i]].push_back(i);
        else{
            flag[*mp[-arr[i]].begin()] = true;
            mp[-arr[i]].erase(mp[-arr[i]].begin());
        }
	}

	vector<int> bestarr;

	for(int i = 0; i < n; i++){
        if(flag[i]){
            bestarr.push_back(-abs(arr[i]));
            bestarr.push_back(abs(arr[i]));
        }
    }

	return findcnt(arr, bestarr);
}

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