Submission #1292488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292488		MMihalev	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1106 ms	205472 KiB

shoes

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include "shoes.h"
using namespace std;
const int MAX_N=3e5+5;
deque<int>le,re[MAX_N];
int tree[MAX_N];
int N;
void Update(int pos)
{
    pos++;
    for(;;)
    {
        if(pos>N)break;
        tree[pos]++;
        pos+=((pos)&(-pos));
    }
}
int Find(int pos)
{
    int res=0;
    pos++;
    for(;;)
    {
        if(pos<1)break;
        res+=tree[pos];
        pos-=((pos)&(-pos));
    }
    return res;
}
int pos[MAX_N];
long long count_swaps(std::vector<int> s)
{
    N=2*s.size();
    long long ans=0;
    int col;

    for(int i=0;i<s.size();i++)
    {
        pos[i]=i;
        if(s[i]<0)le.push_back(i);
        else re[s[i]].push_back(i);
    }

    for(int i=0;i<s.size();i++)
    {
        if(i%2==0)
        {
            int p;
            for(int j=i;j<s.size();j++)
            {
                if(s[j]<0)
                {
                    p=j;
                    break;
                }
            }

            for(int j=p;j>i;j--)
            {
                swap(s[j],s[j-1]);
                ans++;
            }

            col=-s[i];
        }
        else
        {
            int p;
            for(int j=i;j<s.size();j++)
            {
                if(s[j]==col)
                {
                    p=j;
                    break;
                }
            }

            for(int j=p;j>i;j--)
            {
                swap(s[j],s[j-1]);
                ans++;
            }
        }
    }

    return ans;

    for(int i=0;i<s.size();i++)
    {
        int wh=i%2;
        if(wh==0)
        {
            ans+=pos[le.front()]-i;
            col=-s[le.front()];
            for(int j=le.front()-1;pos[j]>=i;j--)pos[j]++;
            le.pop_front();
        }
        else
        {
            ans+=pos[re[col].front()]-i;
            for(int j=re[col].front()-1;pos[j]>=i;j--)pos[j]++;
            re[col].pop_front();
        }
    }

    return ans;
}

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