Submission #1178498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178498		sleepntsheep	Boxes with souvenirs (IOI15_boxes)	C11	0 / 100	1 ms	328 KiB

boxes

#include "boxes.h"
#include <stdio.h>

int n, t1[1111111], t2[1111111];

void add(int*t,int p,int k){
    for(;p<n;p|=p+1)t[p]+=k;
}
int sum(int*t,int p){
    int z=0;
    for(;p;p&=p-1)z+=t[p-1];
    return z;
}
int lowerbound(int*t,int sum){
    int pos=0;
    for(int j=1<<21;j/=2;)
        if(pos+j<=n&&t[pos+j-1]<sum)pos+=j,sum-=t[pos-1];
    return pos;
}

long long delivery(int N, int K, int L, int p[]) {
    long long z=0;
    n=L;
    for(int i=0;i<N;++i){
        if(p[i]==0)continue;
        add(t1,p[i],1), add(t2,L-p[i],1);
    }

    for(;N;){
        int take=N<K?N:K,y1=lowerbound(t1,take),y2=lowerbound(t2,take);
        if(y1<y2){
            for(int i=0;i<K&&N;++i){
                int at=lowerbound(t1,1);
                add(t1,at,-1),add(t2,L-at,-1);
                --N;
            }
            z+=y1;
        }else{
            for(int i=0;i<K&&N;++i){
                int at=lowerbound(t2,1);
                add(t2,at,-1),add(t1,L-at,-1);
                --N;
            }
            z+=y2;
        }
    }

    return 2*z;
}

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