Submission #1105800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105800		snpmrnhlol	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	42 ms	29460 KiB

shoes

#include "shoes.h"
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5;
int fen[2*N];
vector <int> pos[N];
vector <int> pos2[N];
int pt[N];
int n;
void add(int pos, int x){
    for(int i = pos;i < n;i|=(i + 1)){
        fen[i]+=x;
    }
}
int get(int pos){
    int r = 0;
    for(int i = pos;i >= 0;i&=(i + 1),i--){
        r+=fen[i];
    }
    return r;
}
long long count_swaps(std::vector<int> s){
    n = s.size();
    for(int i = 0;i < n;i++){
        if(s[i] > 0){
            pt[i] = (int)pos[s[i] - 1].size();
            pos[s[i] - 1].push_back(i);
        }else{
            pt[i] = (int)pos2[-s[i] - 1].size();
            pos2[-s[i] - 1].push_back(i);
        }
        add(i, 1);
    }
    ll ans = 0;
    for(int i = 0;i < n;i++){
        int id1 = pos[(s[i] > 0?s[i] - 1:-s[i] - 1)][pt[i]];
        int id2 = pos2[(s[i] > 0?s[i] - 1:-s[i] - 1)][pt[i]];
        //cout<<id1<<' '<<id2<<'\n';
        if(id2 < id1)swap(id2,id1);
        if(id2 == i)continue;
        add(id1, -1);
        add(id2, -1);
        ans+=get(id2);
        if(s[id1] > 0)ans++;
    }
	return ans;
}

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