Submission #13377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13377	2015-02-14T09:31:17 Z	dohyun0324	Mountain Trek Route (IZhO12_route)	C++	95 / 100	503 ms	9800 KB

route

#include<stdio.h>
#include<queue>
using namespace std;
typedef pair<int,int> ppair;
int len,n,k,a[1000010],pos[1000010];
long long dap,t;
priority_queue<ppair,vector<ppair>,greater<ppair> >q;
int main()
{
    int i,p,s1,s2;
    scanf("%d %d",&n,&k);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    a[0]=a[n+1]=2147483647;
    for(i=1;i<=n;i++)
    {
        if(a[i]!=a[i-1]) p=i;
        if(a[i]!=a[i+1])
        {
            pos[p]=i; pos[i]=p;
            if(a[i+1]>a[i] && a[p-1]>a[p])
            {
                if(p==1 || i==n) continue;
                q.push(make_pair(i-p+1,p));
            }
        }
    }
    if(a[n]==a[1])
    {
        if(a[pos[n]-1]>a[n] && a[n]<a[pos[1]+1]) q.push(make_pair(n-pos[n]+1+pos[1],pos[n]));
        pos[pos[n]]=pos[1];
    }
    else if(a[n]>a[1] && a[1]<a[2]) q.push(make_pair(pos[1],1));
    else if(a[n]<a[1] && a[n]<a[n-1]) q.push(make_pair(n-pos[n]+1,pos[n]));
    while(1)
    {
        a[0]=a[n]; a[n+1]=a[1]; pos[0]=pos[n]; pos[n+1]=pos[1];
        len=q.top().first; p=q.top().second;
        q.pop();
        if(s1==s2 || len>=n) break;
        if(a[p-1]<a[pos[p]+1])
        {
            t+=len*(a[p-1]-a[p]);
            if(t>=k)
            {
                t-=len*(a[p-1]-a[p]);
                dap+=(k-t)/len;
                break;
            }
            dap+=a[p-1]-a[p];
            s1=pos[p-1]; s2=pos[p];
            pos[s1]=s2; pos[s2]=s1;
            a[s2]=a[p-1];
            if(a[s1-1]>a[s2] && a[s2]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
            if(a[s1-1]>a[s2] && a[s2]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
        }
        else if(a[p-1]>a[pos[p]+1])
        {
            t+=len*(a[pos[p]+1]-a[p]);
            if(t>=k)
            {
                t-=len*(a[pos[p]+1]-a[p]);
                dap+=(k-t)/len;
                break;
            }
            dap+=a[pos[p]+1]-a[p];
            s1=p; s2=pos[pos[p]+1];
            a[s1]=a[pos[p]+1];
            pos[s1]=s2; pos[s2]=s1;
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
        }
        else
        {
            t+=len*(a[pos[p]+1]-a[p]);
            if(t>=k)
            {
                t-=len*(a[pos[p]+1]-a[p]);
                dap+=(k-t)/len;
                break;
            }
            dap+=a[pos[p]+1]-a[p];
            s1=pos[p-1]; s2=pos[pos[p]+1];
            pos[s1]=s2; pos[s2]=s1;
            a[s1]=a[pos[p]+1];
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
        }
    }
    printf("%lld",dap*2);
    return 0;
}

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9028 KB	Output is correct
2	Correct	0 ms	9028 KB	Output is correct
3	Correct	0 ms	9028 KB	Output is correct
4	Correct	0 ms	9028 KB	Output is correct
5	Correct	0 ms	9028 KB	Output is correct
6	Correct	0 ms	9028 KB	Output is correct
7	Correct	0 ms	9028 KB	Output is correct
8	Correct	0 ms	9028 KB	Output is correct
9	Correct	0 ms	9028 KB	Output is correct
10	Correct	21 ms	9028 KB	Output is correct
11	Correct	23 ms	9800 KB	Output is correct
12	Incorrect	503 ms	9028 KB	Output isn't correct
13	Correct	161 ms	9028 KB	Output is correct
14	Correct	183 ms	9028 KB	Output is correct
15	Correct	101 ms	9028 KB	Output is correct
16	Correct	160 ms	9028 KB	Output is correct
17	Correct	150 ms	9028 KB	Output is correct
18	Correct	158 ms	9028 KB	Output is correct
19	Correct	164 ms	9028 KB	Output is correct
20	Correct	97 ms	9028 KB	Output is correct