Submission #1283276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283276		cris71	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	76 ms	135052 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
int const lmax=2e5+7;
vector<int> w;
queue <int> qplus[lmax/2],qminus[lmax/2];
int aib[lmax],n,v[lmax];
int query(int pos)
{
    pos++;
    int sum=0;
    for(int i=pos;i>0;i-=(i&-i))
    {
        sum+=aib[i];
    }
    return sum;
}
void update(int pos, int val)
{
    pos++;
    for(int i=pos;i<=n;i+=(i&-i))
    {
        aib[i]+=val;
    }
}
void debug()
{
    for(int i=0;i<n;i++)cout<<v[i]<<" ";
    cout<<"\n";
}
int count_swaps(vector<int> vv)
{
    int ans=0;
    n=vv.size();
    for(int i=0;i<n;i++)v[i]=vv[i];
    for(int i=0;i<n;i++)update(i,1);
    //debug();
    for(int i=0;i<n;i++)
    {
        if(v[i]>0)qplus[v[i]].push(i);
        else qminus[-v[i]].push(i);
    }
    ///the mappings
    for(int i=0;i<n;i++)
    {
        if((query(i)-query(i-1))==0 or qplus[abs(v[i])].empty()==true)continue;
        int a,b;
        if(v[i]>0)
        {
            a=qplus[v[i]].front();///i
            b=qminus[v[i]].front();
            qplus[v[i]].pop();
            qminus[v[i]].pop();
        }
        else
        {
            a=qminus[-v[i]].front();///i
            b=qplus[-v[i]].front();
            qplus[-v[i]].pop();
            qminus[-v[i]].pop();
        }
        cout<<a<<" "<<b<<"\n";
        ///i in vector -> i+1 in aib
        ///a=i, b=i+h, b>a
        ans+=(query(b-1)-query(a));
        if(v[i]>0)ans++;
        update(b,-1);
        update(a,-1);///does not help at least i dont think
    }


    return ans;
}

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