Submission #494489

#	Time	Username	Problem	Language	Result	Execution time	Memory
494489		Ronin13	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1090 ms	2636 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;
map<int,int>mpi;
map<int,vector<int> >mp;
const int NMAX=200001;
vector<int>a(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>vec;
    for(int i=0;i<s.size();i++){
        int to=s[i];
        mp[to].pb(i+1);

        int x=mp[to].size(),y=mp[-to].size();
        if(x-1==y)vec.pb(to);
    }
    //cout<<1<<"\n";
    int ind=1;
    vector<int>pos(n+1);
    for(int to:vec){
        to=-abs(to);
        int ind1=mpi[to];
        pos[mp[to][ind1]]=ind++;
        pos[mp[-to][ind1]]=ind++;
        mpi[to]++;mpi[-to]++;
    }
    //cout<<1<<"\n";
    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:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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