제출 #143919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143919		daniel920712	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1071 ms	153736 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];
int a[200005];
int b[200005];
int now=1;
map < int , deque < int > > all1;
map < int , deque < int > > all2;
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)
{
    //printf("a %d\n",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;
}

long long count_swaps(std::vector<int> S)
{
    long long ans1=0,small,what,t,a,b;
    int i,j,k,N=S.size();
    build(0,N-1,0);
    for(i=0;i<N/2;i++) if(!(S[i]<0&&0-S[i]==S[i+N/2])) break;
    //if(i==N/2) return ((long long) N/2)*((long long) N/2-1)/2;
    for(i=0;i<N;i++)
    {
        if(S[i]<0) all1[0-S[i]].push_back(i);
        else all2[S[i]].push_back(i);
    }
    //printf("aa");
    for(i=0;i<N/2;i++)
    {
        small=1000000000;
        for(auto j:all1)
        {
            //printf("%d %d %d\n",j.first,all1[j.first].front(),all2[j.first].front());
            a=all1[j.first].front()+Find(all1[j.first].front(),0);
            b=all2[j.first].front()+Find(all2[j.first].front(),0);
            t=a+b;
            if(a>b) t++;
            if(t<small)
            {
                small=t;
                what=j.first;
            }
        }
        //printf("%lld %lld\n",what,small);
        ans1+=(small-i*2-i*2-1);
        change(0,all1[what].front(),0);
        change(0,all2[what].front(),0);
        all1[what].pop_front();
        all2[what].pop_front();
        if(all1[what].empty())
        {
            all1.erase(what);
            all2.erase(what);
        }
    }


    return ans1;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:60:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,k,N=S.size();
           ^
shoes.cpp:60:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k,N=S.size();
             ^
shoes.cpp: In function 'int Find(int, int)':
shoes.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:88:27: warning: 'what' may be used uninitialized in this function [-Wmaybe-uninitialized]
         change(0,all1[what].front(),0);
                           ^

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