제출 #1282069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282069		xorreverse	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	57 ms	14628 KiB

shoes

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

vector<int> left_shoose[100005];
vector<int> right_shoose[100005];
bool cmp(pair<int, int> a, pair<int, int>b){
    return (a.first + a.second + (a.first > a.second)) < (b.first + b.second + (b.first > b.second));
}
int fen[200005];
void up(int idx, int chg){
    while (idx <= 200000){
        fen[idx] += chg;
        idx += idx & (-idx);
    }
    return;
}
int re(int idx){
    int res = 0;
    while (idx > 0){
        res += fen[idx];
        idx -= idx & (-idx);
    }
    return res;
}
long long count_swaps(vector<int> s){
    int n = s.size() / 2;
    for (int i = 0; i < 2 * n; i ++){
        if (s[i] < 0) left_shoose[-s[i]].push_back(i + 1);
        else right_shoose[s[i]].push_back(i + 1);
    }
    vector<pair<int, int>> sigma;
    for (int i = 1; i <= n; i ++){
        while (right_shoose[i].size()){
            sigma.push_back({left_shoose[i].back(), right_shoose[i].back()});
            right_shoose[i].pop_back();
            left_shoose[i].pop_back();
        }
    }
    sort(sigma.begin(), sigma.end(), cmp);
    long long res = 0;
    for (int i = 0; i <n; i ++){
        int left_val = sigma[i].first + re(sigma[i].first);
        int right_val = sigma[i].second + re(sigma[i].second);
        up(1, 1);
        up(sigma[i].first, -1);
        up(1, 1);
        up(sigma[i].second, -1);
        res += left_val + right_val;
        if (left_val > right_val) res ++;
        res -= 2 * i + 1;
        res -= 2 * i + 2;
    }
    return res;
}

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