제출 #914963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914963		Gabriel	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1094 ms	12632 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
bool Ordenado(vector<int> s){
    bool S_ = 1;
    for(long long i = 0; i < (long long)s.size(); i += 2){ if(!(s[i] < 0 and s[i + 1] == -s[i])) S_ = 0; cout<<s[i]<<" "<<s[i + 1]<<" "; }
    cout<<"\n";
    return S_;
}
vector<long long> _rbol;
vector<long long> Jaja;
vector<long long> m;
void Crear(long long Izquierda, long long Derecha, long long Posici_n){
    if(Izquierda == Derecha){
        _rbol[Posici_n] = m[Izquierda];
        Jaja[Izquierda] = Posici_n;
    } else {
        long long Promedio = (Izquierda + Derecha) / 2;
        Crear(Izquierda, Promedio, Posici_n * 2);
        Crear(Promedio + 1, Derecha, Posici_n * 2 + 1);
        _rbol[Posici_n] = _rbol[Posici_n * 2] + _rbol[Posici_n * 2 + 1];
    }
}
long long Consulta(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
    if(Izquierda >= Inicio and Derecha <= Final) return _rbol[Posici_n];
    else if(Izquierda > Final or Derecha < Inicio) return 0;
    else {
        long long Promedio = (Izquierda + Derecha) / 2;
        return Consulta(Izquierda, Promedio, Posici_n * 2, Inicio, Final) + Consulta(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final);
    }
}
void Actualizar(long long Posici_n, long long Valor, long long Original){
    if(Posici_n == 0) return;
    if(Posici_n == Original) _rbol[Posici_n] = Valor;
    else _rbol[Posici_n] = _rbol[Posici_n * 2] + _rbol[Posici_n * 2 + 1];
    Actualizar(Posici_n / 2, Valor, Original);
}
long long count_swaps(vector<int> s){
    long long n = s.size();
    /*if(n == 2){
        if(s[0] < 0) return 0;
        else return 1;
    } else if(n <= 2222222){*/
        /*long long Contador = 0;
        for(long long i = 0; i < n; i++){
            if(i % 2 == 0){
                if(s[i] > 0){
                    for(long long j = i; j < n; j++){
                        if(s[j] == -s[i]){
                            for(long long k = j; k > i; k--){
                                swap(s[k], s[k - 1]);
                                Contador++;
                            }
                            break;
                        }
                    }
                }
            } else {
                if(!(s[i] == -s[i - 1] and s[i] > 0)){
                    for(long long j = i; j < n; j++){
                        if(s[j] == -s[i - 1]){
                            for(long long k = j; k > i; k--){
                                swap(s[k], s[k - 1]);
                                Contador++;
                            }
                            break;
                        }
                    }
                }
            }
        }
        return Contador;*/
        m.assign(n, 1);
        Jaja.assign(n, 0);
        _rbol.assign(n * 4, 0);
        n--;
        Crear(0, n, 1);
        long long Contador = 0;
        for(long long i = 0; i <= n; i++){
            if(m[i] == 1){
                /*if(i % 2 == 0){
                    if(s[i] > 0){*/
                        for(long long j = i + 1; j <= n; j++){
                            if(m[j] == 1){
                                if(s[j] == -s[i]){
                                    m[j] = 0;
                                    Actualizar(Jaja[j], 0, Jaja[j]);
                                    Contador += Consulta(0, n, 1, i, j - 1);
                                    if(s[i] < 0) Contador--;
                                    //cout<<i<<" "<<j<<" "<<Contador<<"\n";
                                    break;
                                }
                            }
                        }
                    /*}
                } else {
                    if(!(s[i] == -s[i - 1] and s[i] > 0)){
                        for(long long j = i; j <= n; j++){
                            if(m[i] == 1){
                                if(s[j] == -s[i - 1]){
                                    m[i] = 0;
                                    Actualizar(Jaja[i], 0, Jaja[i]);
                                    Contador += Consulta(0, n, 1, i, j - 1);
                                    break;
                                }
                            }
                        }
                    }
                }*/
            }
            m[i] = 0;
            Actualizar(Jaja[i], 0, Jaja[i]);
        }
        return Contador;
    /*} else {
        n /= 2;
        return n * (n - 1) / 2;

    }*/
}

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