Submission #144549

#	Time	Username	Problem	Language	Result	Execution time	Memory
144549		daniel920712	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	440 ms	32572 KiB

shoes

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <map>
#include <deque>

using namespace std;

struct A
{
    int l,r;
    int nxl,nxr;
    int how;
}Node[1000005];
struct B
{
    int x,y;
}all[1000005];
int a[200005];
int b[200005];
int now=1;
map < int , vector < int > > all3;
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].how=0;
    if(l==r) return;

    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
}
void change(int l,int r,int here)
{
    if(l==Node[here].l&&r==Node[here].r)
    {
        Node[here].how++;
        return;
    }
    if(r<=(Node[here].l+Node[here].r)/2) change(l,r,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) change(l,r,Node[here].nxr);
    else
    {
        change(l,(Node[here].l+Node[here].r)/2,Node[here].nxl);
        change((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr);
    }
}
int Find(int where,int here)
{
    if(where==Node[here].l&&where==Node[here].r) return Node[here].how;
    if(where<=(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxl)+Node[here].how;
    else if(where>(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxr)+Node[here].how;
}
bool F(B a,B b)
{
    int x=0,y=0;
    x=a.x+a.y;
    y=b.x+b.y;
    if(a.x>a.y) x++;
    if(b.x>b.y) y++;
    return x<y||x==y&&min(a.x,a.y)<min(b.x,b.y);
}
long long count_swaps(std::vector<int> S)
{
    long long ans1=0,small,what,t,a,b;
    int i,j,k,N=S.size(),x=0,M;
    build(0,N-1,0);
    for(i=0;i<N;i++)
    {
        all3[S[i]].push_back(i);
        //printf("%d %d %d\n",i,S[i],all3[S[i]].back());
    }
    for(i=1;i<=N/2;i++)
    {
        M=all3[i].size();
        for(j=0;j<M;j++)
        {
            all[x].x=all3[0-i][j];
            all[x].y=all3[i][j];
            //printf("%d %d %d %d\n",i,j,all3[i][j],all3[0-i][j]);
            x++;
        }
    }
    sort(all,all+N/2,F);
    for(i=0;i<N/2;i++)
    {
        //printf("%d %d\n",all[i].x,all[i].y);
        ans1+=Find(all[i].x,0)+Find(all[i].y,0)+all[i].x+all[i].y-i*2-i*2-1;
        if(all[i].x>all[i].y) ans1++;
        change(0,all[i].x,0);
        change(0,all[i].y,0);
    }
    return ans1;
}

Compilation message (stderr)

shoes.cpp: In function 'bool F(B, B)':
shoes.cpp:65:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return x<y||x==y&&min(a.x,a.y)<min(b.x,b.y);
                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:69:22: warning: unused variable 'small' [-Wunused-variable]
     long long ans1=0,small,what,t,a,b;
                      ^~~~~
shoes.cpp:69:28: warning: unused variable 'what' [-Wunused-variable]
     long long ans1=0,small,what,t,a,b;
                            ^~~~
shoes.cpp:69:33: warning: unused variable 't' [-Wunused-variable]
     long long ans1=0,small,what,t,a,b;
                                 ^
shoes.cpp:69:35: warning: unused variable 'a' [-Wunused-variable]
     long long ans1=0,small,what,t,a,b;
                                   ^
shoes.cpp:69:37: warning: unused variable 'b' [-Wunused-variable]
     long long ans1=0,small,what,t,a,b;
                                     ^
shoes.cpp:70:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k,N=S.size(),x=0,M;
             ^
shoes.cpp: In function 'int Find(int, int)':
shoes.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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