Submission #526469

#	Time	Username	Problem	Language	Result	Execution time	Memory
526469		Deepesson	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	249 ms	77848 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){
    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::vector<int> ordem;
    std::map<int,std::queue<int>> mapa;
    for(int i=0;i!=s.size();++i){
        if(s[i]>0){
            mapa[s[i]].push(i);
        }else ordem.push_back(i);
    }
    int cur=0;
    for(auto&x:ordem){
        posicoes[x]=cur;
        int val = abs(s[x]);
        posicoes[mapa[val].front()]=cur+1;
        mapa[val].pop();
        cur+=2;
    }
	return num_inversoes(posicoes);
}

Compilation message (stderr)

shoes.cpp: In function 'long long int num_inversoes(std::vector<int>)':
shoes.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     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){
      |                 ~^~~~~~~~~~

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