Submission #13376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13376	2015-02-14T07:54:15 Z	dohyun0324	Mountain Trek Route (IZhO12_route)	C++	15 / 100	2000 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])
    {
        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) 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]) q.push(make_pair(s2-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];
            pos[s1]=s2; pos[s2]=s1;
            a[s1]=a[pos[p]+1];
            if(a[s1-1]>a[s1] && a[s1]<a[s2+1]) q.push(make_pair(s2-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]) q.push(make_pair(s2-s1+1,s1));
        }
    }
    printf("%lld",dap*2);
    return 0;
}

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	9028 KB	Output isn't correct
2	Correct	0 ms	9028 KB	Output is correct
3	Incorrect	0 ms	9028 KB	Output isn't correct
4	Correct	0 ms	9028 KB	Output is correct
5	Incorrect	0 ms	9028 KB	Output isn't correct
6	Execution timed out	2000 ms	9024 KB	Program timed out
7	Incorrect	0 ms	9028 KB	Output isn't correct
8	Incorrect	0 ms	9028 KB	Output isn't correct
9	Incorrect	0 ms	9028 KB	Output isn't correct
10	Incorrect	15 ms	9028 KB	Output isn't correct
11	Correct	0 ms	9800 KB	Output is correct
12	Incorrect	0 ms	9028 KB	Output isn't correct
13	Incorrect	202 ms	9028 KB	Output isn't correct
14	Incorrect	192 ms	9028 KB	Output isn't correct
15	Incorrect	220 ms	9028 KB	Output isn't correct
16	Incorrect	126 ms	9028 KB	Output isn't correct
17	Execution timed out	2000 ms	9024 KB	Program timed out
18	Execution timed out	2000 ms	9024 KB	Program timed out
19	Incorrect	193 ms	9028 KB	Output isn't correct
20	Execution timed out	2000 ms	9024 KB	Program timed out