Submission #13378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13378	2015-02-14T10:58:00 Z	dohyun0324	Mountain Trek Route (IZhO12_route)	C++	100 / 100	194 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]; pos[pos[1]]=pos[n];
    }
    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(dap==20)
        {
            dap=20;
        }
        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

100.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	10 ms	9028 KB	Output is correct
11	Correct	22 ms	9800 KB	Output is correct
12	Correct	12 ms	9028 KB	Output is correct
13	Correct	194 ms	9028 KB	Output is correct
14	Correct	149 ms	9028 KB	Output is correct
15	Correct	99 ms	9028 KB	Output is correct
16	Correct	161 ms	9028 KB	Output is correct
17	Correct	161 ms	9028 KB	Output is correct
18	Correct	163 ms	9028 KB	Output is correct
19	Correct	161 ms	9028 KB	Output is correct
20	Correct	138 ms	9028 KB	Output is correct