제출 #614021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
614021		AlperenT	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	942 ms	294468 KiB

shoes

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

using namespace std;

const int N = 4e5 + 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;

long long findcnt(vector<int> a, vector<int> b){
    map<int, deque<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]].front(); nums[a[i]].pop_front();
        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, deque<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]].front()] = true;
            mp[-arr[i]].pop_front();
        }
	}

	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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15