Submission #1834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1834		alephnull	공장 (KOI13_factory)	C++98	20 / 20	311 ms	14488 KiB

factory

#include <cstdio> 
#include <algorithm> 
using namespace std; 
long long merge(int *a,int *b,int n1,int n2,int *tmp){ 
    long long ret=0; 
    int i=0,ia=0,ib=0; 
    while(ia<n1&&ib<n2){ 
        if(a[ia]<=b[ib]) 
            tmp[i++]=a[ia++]; 
        else{ 
            tmp[i++]=b[ib++]; 
            ret+=n1-ia; 
        } 
    } 
    while(ia<n1) 
        tmp[i++]=a[ia++]; 
    while(ib<n2){ 
        tmp[i++]=b[ib++]; 
        ret+=n1-ia; 
    } 
    return ret; 
} 
long long rev(int* a,int n){ 
    if(n==1)return 0; 
    long long ret=0; 
    int a1[(n+1)/2],a2[n/2]; 
    for(int i=0;i<(n+1)/2;i++)a1[i]=a[i]; 
    for(int i=0;i<n/2;i++)a2[i]=a[(n+1)/2+i]; 
    ret+=rev(a1,(n+1)/2); 
    ret+=rev(a2,n/2); 
    ret+=merge(a1,a2,(n+1)/2,n/2,a); 
    return ret; 
} 
int main(){ 
    int n;scanf("%d",&n); 
    int a[n]; 
    int b[n]; 
    int* hash=new int[1000001]; 
    int p[n]; 
    for(int i=0;i<n;i++){ 
        scanf("%d",a+i); 
        hash[a[i]]=i; 
    } 
    for(int i=0;i<n;i++) 
        scanf("%d",b+i); 
    for(int i=0;i<n;i++) 
        p[hash[b[i]]]=i; 
    printf("%lld",rev(p,n)); 
} 

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8