Submission #537835

#	Time	Username	Problem	Language	Result	Execution time	Memory
537835		andrei_boaca	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	264 ms	151988 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
ll ans=0;
ll n,v[200005],aib[200005];
deque<ll> poz[100005][2]; // 0 - negative      1 positive
ll lsb(ll x)
{
    return x&(-x);
}
void update(ll poz,ll val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
ll suma(ll poz)
{
    ll rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
ll count_swaps(vector<int> S)
{
    n=S.size();
    for(int i=0;i<S.size();i++)
        v[i+1]=S[i];
    for(int i=1;i<=n;i++)
    {
        ll val=abs(v[i]);
        if(v[i]<0)
            poz[val][0].push_back(i);
        else
            poz[val][1].push_back(i);
    }
    vector<int> sol;
    set<int> s;
    for(int i=1;i<=n;i++)
        s.insert(i);
    for(int i=1;i<=n;i++)
    {
        ll index=*s.begin();
        ll val=v[index];
        if(i%2==1)
        {
            if(val<0)
            {
                s.erase(index);
                sol.push_back(val);
                update(index+1,1);
                poz[-val][0].pop_front();
                continue;
            }
            sol.push_back(-val);
            ll p=poz[val][0].front();
            poz[val][0].pop_front();
            s.erase(p);
            ans+=p-suma(p)-1;
            update(p+1,1);
        }
        else
        {
            ll need=-sol.back();
            sol.push_back(need);
            if(val==need)
            {
                s.erase(index);
                update(index+1,1);
                poz[val][1].pop_front();
                continue;
            }
            ll p=poz[need][1].front();
            poz[need][1].pop_front();
            s.erase(p);
            ans+=p-suma(p)-1;
            update(p+1,1);
        }
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(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<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