Submission #1046496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046496		Dalek_of_Rivia	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	234 ms	82256 KiB

shoes

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

using namespace std;

int H[550000];

void build(int n){
    for(int i=1; i<=n; i++){
        H[i]=0;
    }
    for(int i=n+1; i>0; i--){
        H[i+n]=0;
    }
}

void actualizar(int s, int nodo, int n){
    if(nodo<275000){
        int u=(n+1)/2;
        if(s>=u){
            H[2*nodo]++;
            actualizar(s-u, 2*nodo+1, n-u);
        }else{
            actualizar(s, 2*nodo, u);
        }
    }
}

int evaluar(int s, int nodo, int n){
    if(nodo<275000){
        int u=(n+1)/2;
        if(s>=u){
            return (int)H[nodo]+evaluar(s-u, 2*nodo+1, n-u);
        }else{
            return (int)H[nodo]+evaluar(s, 2*nodo, u);
        }
    }
    return H[nodo];
}

long long count_swaps(vector<int> s) {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
	map<int, queue<int>> m;
    map<int, bool> b;
    long long ans = 0;
    int N = s.size();
    for(int i=0; i<N; i++){
        int K = abs(s[i]);
        if(!m[K].empty()){
            if(s[i]>0){
                if(b[K]){
                    m[K].push(i);
                }else{
                    ans+=i-m[K].front()-1;
                    s[i]=-1;
                    s[m[K].front()]=i+1;
                    m[K].pop();
                }
            }else{
                if(!b[K]){
                    m[K].push(i);
                }else{
                    ans+=i-m[K].front()+1;
                    s[i]=-1;
                    s[m[K].front()]=i+1;
                    m[K].pop();
                }
            }
        }else{
            m[K].push(i);
            b[K]=(s[i]>0);
        }
    }
    ans/=2;
    int P=1;
    int ka=N;
    while(ka>0){
        ka=ka/2;
        P*=2;
    }
    build(P);
    for(int i=0; i<N; i++){
        if(s[i]!=-1){
            ans+=evaluar(s[i], 1, P);
            actualizar(s[i], 1, P);
        }
    }
    return ans;
}

/*int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int T;
    cin>>T;
    for(int dalekofrivia=T; dalekofrivia>0; dalekofrivia--){
        int n;
        cin>>n;
        vector<int> s;
        for(int i=0; i<2*n; i++){
            int u;
            cin>>u;
            s.push_back(u);
        }
        cout<<count_swaps(s)<<endl;
    }
    return 0;
}*/

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