Submission #494499

#	Time	Username	Problem	Language	Result	Execution time	Memory
494499		Ronin13	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	424 ms	32588 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX=200001;
int mpi[NMAX];
map<int,int>mp1;
vector<vector<int> >a(2*NMAX);

vector<ll>f(NMAX);
int lsb(int x){
    return x&-x;
}

ll sum(int pos){
    ll ss=0;
    while(pos){
        ss+=f[pos];
        pos-=lsb(pos);
    }
    return ss;
}
int n;
void add(int pos,ll val){
    while(pos<=n){
        f[pos]+=val;
        pos+=lsb(pos);
    }
}

long long count_swaps(std::vector<int> s) {
    n=s.size();
    vector<int>ff;
    for(int i=0;i<s.size();i++)ff.pb(s[i]);
    for(int i=0;i<ff.size();i++)mp1[ff[i]]=i+1;
    vector<int>vec;
    for(int i=0;i<s.size();i++){
        int to=s[i];
        int to1=-s[i];
        to=mp1[to],to1=mp1[to1];
        a[to].pb(i+1);

        int x=a[to].size(),y=a[to1].size();
        if(x>y)vec.pb(s[i]);
    }

    int ind=1;
    vector<int>pos(n+1);
    for(int to:vec){
        to=-abs(to);
        int to1=-to;
        to=mp1[to];to1=mp1[to1];
        int ind1=mpi[to];
        pos[a[to][ind1]]=ind++;
        pos[a[to1][ind1]]=ind++;
        mpi[to]++;mpi[to1]++;
    }

    ll sss=0;
    for(int i=0;i<(int)s.size();i++){
        int x=pos[i+1];
        if(x!=n){
            sss+=sum(n)-sum(x);
        }
        add(x,1);
    }
    return sss;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<s.size();i++)ff.pb(s[i]);
      |                 ~^~~~~~~~~
shoes.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<ff.size();i++)mp1[ff[i]]=i+1;
      |                 ~^~~~~~~~~~
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