Submission #432264

#	Time	Username	Problem	Language	Result	Execution time	Memory
432264		Amylopectin	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	211 ms	63592 KiB

shoes

#include <iostream>
#include <stdio.h>
#include <vector>
#include "shoes.h"
//#include "grader.cpp"
using namespace std;
const long long mxn = 2e6 + 10;
vector <long long> li[mxn] = {};
long long ta[mxn] = {},se[mxn] = {},u[mxn] = {},cou[mxn] = {};
long long cre(long long cl,long long cr,long long no)
{
    if(cl == cr)
    {
        se[no] = 1;
        return 0;
    }
    long long mid = (cl+cr) / 2;
    cre(cl,mid,no*2);
    cre(mid+1,cr,no*2+1);
    se[no] = se[no*2] + se[no*2+1];
    return 0;
}
long long del(long long cl,long long cr,long long no,long long tn)
{
    if(cr < tn || cl > tn)
    {
        return 0;
    }
    if(cl == cr)
    {
        se[no] = 0;
        return 0;
    }
    long long mid = (cl+cr) / 2;
    del(cl,mid,no*2,tn);
    del(mid+1,cr,no*2+1,tn);
    se[no] = se[no*2] + se[no*2+1];
    return 0;
}
long long fisu(long long cl,long long cr,long long no,long long tn)
{
    if(cl > tn)
    {
        return 0;
    }
    if(cr <= tn)
    {
        return se[no];
    }
    long long mid = (cl+cr) / 2,su = 0;
    su += fisu(cl,mid,no*2,tn);
    su += fisu(mid+1,cr,no*2+1,tn);
    return su;
}
long long count_swaps(vector<int> s)
{
    long long i,j,n = s.size(),cpo,ans = 0;
    cre(0,n-1,1);
    for(i=0; i<n; i++)
    {
        if(s[i] > 0)
        {
            li[s[i]*2].push_back(i);
        }
        else
        {
            li[(-s[i] * 2) + 1].push_back(i);
        }
    }
    for(i=0; i<n; i++)
    {
        if(u[i] == 0)
        {
            if(s[i] > 0)
            {
                cpo = li[s[i]*2+1][cou[s[i]*2+1]];
                cou[s[i]*2+1] ++;
                cou[s[i]*2] ++;
                ans += fisu(0,n-1,1,cpo-1);
            }
            else
            {
                cpo = li[(-(s[i]*2))][cou[-s[i]*2]];
                cou[-s[i]*2] ++;
                cou[(-s[i]*2)+1] ++;
                ans += fisu(0,n-1,1,cpo-1)-1;
            }
            del(0,n-1,1,cpo);
            del(0,n-1,1,i);
            u[i] = 1;
            u[cpo] = 1;
        }
    }
	return ans;
}
//long long main()
//{
//
//    return 0;
//}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:57:17: warning: unused variable 'j' [-Wunused-variable]
   57 |     long long i,j,n = s.size(),cpo,ans = 0;
      |                 ^

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