Submission #221773

#	Time	Username	Problem	Language	Result	Execution time	Memory
221773		mathking1021	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	278 ms	275708 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <queue>

typedef long long ll;
using namespace std;

const ll M = 200000;
queue<ll> qu[400005];
ll d[200005];
ll n;

ll f(ll p)
{
    ll re = 0;
    p++;
    while(p > 0)
    {
        re += d[p];
        p -= (p & (-p));
    }
    return re;
}

void g(ll p)
{
    p++;
    while(p <= n)
    {
        d[p]--;
        p += (p & (-p));
    }
}

long long count_swaps(std::vector<int> s)
{
    ll cnt = 0;
    n = s.size();
    for(ll i = 0; i < s.size(); i++)
    {
        qu[s[i] + M].push(i);
        d[i + 1] = ((i + 1) & (-(i + 1)));
    }
    for(ll i = 0; i < s.size(); i++)
    {
        if(qu[M + s[i]].front() != i) continue;
        ll j = qu[M - s[i]].front();
        qu[M - s[i]].pop();
        qu[M + s[i]].pop();
        cnt += f(j) - f(i) - 1;
        g(i), g(j);
        if(s[i] > 0) cnt++;
    }
    return cnt;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < s.size(); i++)
                   ~~^~~~~~~~~~
shoes.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll 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