Submission #779045

#	Time	Username	Problem	Language	Result	Execution time	Memory
779045		mrwang	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	54 ms	25200 KiB

shoes

#include "shoes.h"
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll sz[maxN];
vector<ll>vec[maxN][2];
ll match[maxN],arr[maxN],cnt=0,bit[maxN];
bool vis[maxN];
void update(ll i)
{
    while(i<maxN)
    {
        bit[i]++;
        i+=i&(-i);
    }
}
ll get(ll i)
{
    ll aa=0;
    while(i>0)
    {
        aa+=bit[i];
        i-=i&(-i);
    }
    return aa;
}
long long count_swaps(vector<int> S)
{
    ll n=S.size();
    for(int i=1;i<=n;i++) sz[i]=S[i-1];
    for(int i=1;i<=n;i++)
    {
        if(sz[i]<0)
        {
            vec[-sz[i]][0].pb(i);
        }
        else
        {
            vec[sz[i]][1].pb(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<vec[i][0].size();j++)
        {
            match[vec[i][0][j]]=vec[i][1][j];
            match[vec[i][1][j]]=vec[i][0][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        vis[i]=false;
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==false)
        {
            vis[i]=true;
            vis[match[i]]=true;
            ll pos1,pos2;
            pos1=i;
            pos2=match[i];
            if(sz[i]>0) swap(pos1,pos2);
            arr[cnt+1]=pos1;
            arr[cnt+2]=pos2;
            cnt+=2;
        }
        else continue;
    }
    ll ans=0;
    for(int i=n;i>=1;i--)
    {
        //cout << arr[i]<<' ';
        ans+=get(arr[i]);
        update(arr[i]);
    }
    //cout << '\n';
    return ans;
}
/*void solve()
{
    cout << count_swaps({2, 1, -1, -2});
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int j=0;j<vec[i][0].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~

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