Submission #371221

#	Time	Username	Problem	Language	Result	Execution time	Memory
371221		amano_hina	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	281 ms	56172 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
long long tw[35];
vector<int> v[400010];
vector<int> st[400010];
bitset<400010> fysty;
long long ans=0;
int xx,cnt=0;
int amano_hina[400010];
void joylintp_pretend_weak_every_day_haiyaa(int x)
{
    int n=st[0].size();
    for(int i=0;i<n;i++)
    {
        st[x/tw[i]*tw[i]][i]++;
    }
}
long long wty2016_is_electric(int x)
{
    int n=st[0].size();
    int waynetuinfor=0;
    int ans=0;
    for(int i=n-1;i>=0;i--)
    {
        if(waynetuinfor+tw[i]-1<=x)
        {
            ans+=st[waynetuinfor][i];
            waynetuinfor+=tw[i];
        }
        if(waynetuinfor==x+1)
        {
            break;
        }
    }
    return ans;
}
long long count_swaps(std::vector<int> s) {

    int n=s.size();

    for(int i=0;i<=2*n+1;i++)
    {
        amano_hina[i]=0;
    }

    tw[0]=1;
    for(int i=1;i<=30;i++)
    {
        tw[i]=tw[i-1]*2;
    }
    for(int i=0;i<n;i++)
    {
        v[s[i]+n/2].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        st[i].push_back(0);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=1;;j++)
        {
            if(i+tw[j-1]<n)
            {
                st[i].push_back(0);
            }
            else
            {
                break;
            }
        }
    }
    /*for(int i=0;i<n;i++)
    {
        cout<<i<<" ";
        for(int j=0;j<st[i].size();j++)
        {
            cout<<st[i][j]<<" ";
        }
        cout<<endl;
    }*/

    for(int i=0;i<n;i++)
    {
        if(fysty[i]==0)
        {
            xx=(n/2)-s[i];

            fysty[i]=1;
            //cout<<v[xx][amano_hina[xx]]<<endl;
            fysty[v[xx][amano_hina[xx]]]=1;

            if(s[i]>0)
            {
                ans++;
            }
            ans=ans+v[xx][amano_hina[xx]]-(2*cnt+1);
            ans=ans+wty2016_is_electric(n-1)-wty2016_is_electric(v[xx][amano_hina[xx]]);
            joylintp_pretend_weak_every_day_haiyaa(i);
            joylintp_pretend_weak_every_day_haiyaa(v[xx][amano_hina[xx]]);
            /*for(int i=0;i<n;i++)
            {
                cout<<i<<" ";
                for(int j=0;j<st[i].size();j++)
                {
                    cout<<st[i][j]<<" ";
                }
                cout<<endl;
            }*/
            //cout<<"ans= "<<ans<<endl;
            amano_hina[xx]++;
            amano_hina[s[i]+n/2]++;
            cnt++;
        }

    }
    return ans;

}
/*int main()
{
    int n;
    int x;
    vector<int> i_am_noob;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        i_am_noob.push_back(x);
    }
    cout<<count_swaps(i_am_noob);
}*/

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