Submission #1046468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046468		Dalek_of_Rivia	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	0 ms	348 KiB

shoes

    #include<bits/stdc++.h>
     
    using namespace std;
     
    vector<vector<int>> G;
    int H[100];
     
    void build(int n){
        G.clear();
        vector<int> v;
        v.clear();
        G.push_back(v);
        for(int i=1; i<=n; i++){
            G.push_back(v);
            G[i].push_back(2*i);
            G[i].push_back(2*i+1);
            H[i]=0;
        }
        for(int i=n+1; i>0; i--){
            G.push_back(v);
            H[i+n]=0;
        }
    }
     
    void actualizar(int s, int nodo, int n){
        if(G[nodo].size()>0){
            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(G[nodo].size()>0){
            int u=(n+1)/2;
            if(s>=u){
                return H[nodo]+evaluar(s-u, 2*nodo+1, n-u);
            }else{
                return H[nodo]+evaluar(s, 2*nodo, u);
            }
        }
        return H[nodo];
    }
     
    long long count_swaps(vector<int> s) {
    	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;
        cout<<ans<<endl;
        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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15