Submission #526470

#	Time	Username	Problem	Language	Result	Execution time	Memory
526470		Deepesson	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	486 ms	149700 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define MAX 550000
#define LSB(A) (A&(-A))
int ft[MAX];
void add(int p,int k){
    p+=3;
    while(p<MAX){
        ft[p]+=k;
        p+=LSB(p);
    }
}
int query(int p){
    p+=3;
    int ans=0;
    while(p>0){
        ans+=ft[p];
        p-=LSB(p);
    }
    return ans;
}
int seg(int l,int r){
    return query(r)-query(l-1);
}
long long num_inversoes(std::vector<int> x){
    ///for(auto&z:x)std::cout<<z<<" ";std::cout<<"\n";
    long long ans=0;
    for(int i=0;i!=x.size();++i){
        ans+=seg(x[i]+1,MAX-3);
        add(x[i],1);
    }
    return ans;
}
long long count_swaps(std::vector<int> s) {
    std::vector<int> posicoes(s.size());
    std::map<int,std::queue<int>> mapal,mapar;
    for(int i=0;i!=s.size();++i){
        if(s[i]>0){
            mapar[s[i]].push(i);
        }else mapal[abs(s[i])].push(i);
    }
    bool pegou[s.size()]={};
    int cur=0;
    for(int i=0;i!=s.size();++i){
        if(pegou[i])continue;
        if(s[i]>0){///Direito
            int x;
            for(;;){
                int u = mapal[abs(s[i])].front();
                mapal[abs(s[i])].pop();
                if(!pegou[u]){
                    x=u;
                    break;
                }
            }
            pegou[x]=true;
            pegou[i]=true;
            posicoes[x]=cur;
            posicoes[i]=cur+1;
        }else {///Esquerdo
            int x;
            for(;;){
                int u = mapar[abs(s[i])].front();
                mapar[abs(s[i])].pop();
                if(!pegou[u]){
                    x=u;
                    break;
                }
            }
            pegou[x]=true;
            pegou[i]=true;
            posicoes[x]=cur+1;
            posicoes[i]=cur;
        }
        cur+=2;
    }
	return num_inversoes(posicoes);
}

Compilation message (stderr)

shoes.cpp: In function 'long long int num_inversoes(std::vector<int>)':
shoes.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i!=x.size();++i){
      |                 ~^~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i!=s.size();++i){
      |                 ~^~~~~~~~~~
shoes.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i!=s.size();++i){
      |                 ~^~~~~~~~~~

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