Submission #882000

#	Time	Username	Problem	Language	Result	Execution time	Memory
882000		alexdd	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	514 ms	43888 KiB

route

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
mt19937 rnd(1823764);
int n,k;
int a[1000005];
int inita[1000005];
int root[1000005];
int tole[1000005];
int tori[1000005];
int lun(int x)
{
    if(tole[x]<=tori[x])
        return tori[x]-tole[x]+1;
    else
        return (n-tole[x]+1) + tori[x];
}
priority_queue<pair<int,int>> pq;
void afis()
{
    /*for(int i=1;i<=n;i++)
        cout<<a[root[i]]<<" ";
    cout<<"\n";*/
    /*for(int i=1;i<=n;i++)
    {
        if(i==1 || root[i]!=root[i-1])
        {
            cout<<root[i]<<"  "<<tole[root[i]]<<" "<<tori[root[i]]<<"  "<<a[root[i]]<<"\n";
        }
    }*/
}
void initializeaza_secvente()
{
    if(a[1]==a[n])
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=a[1])
                break;
            root[i]=1;
            tori[1]=i;
        }
        for(int i=n;i>0;i--)
        {
            if(a[i]!=a[n])
                break;
            root[i]=1;
            tole[1]=i;
        }
        int aux = tori[1]+1;
        root[aux] = aux;
        tole[aux] = aux;
        for(int i=tori[1]+2;i<tole[1];i++)
        {
            if(a[i]!=a[i-1])
            {
                tori[aux]=i-1;
                aux=i;
                tole[i]=i;
            }
            root[i]=aux;
        }
        tori[aux]=tole[1]-1;
    }
    else
    {
        int aux=1;
        root[1]=1;
        tole[1]=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]!=a[i-1])
            {
                tori[aux]=i-1;
                aux=i;
                tole[i]=i;
            }
            root[i]=aux;
        }
        tori[aux]=n;
    }
    for(int i=1;i<=n;i++)
    {
        if(root[i]==i)
        {
            int tol = tole[i]-1;
            if(tol==0)
                tol=n;
            int tor = tori[i]+1;
            if(tor==n+1)
                tor=1;
            if(a[tol]>a[i] && a[tor]>a[i])
            {
                pq.push({-lun(i),i});
            }
        }
    }
    //for(int i=1;i<=n;i++)
      //  cout<<root[i]<<" ";
}
void unite(int x, int y)
{
    if(lun(x) <= lun(y))
    {
        tole[y] = tole[x];
        int j = tole[x];
        while(j!=tori[x])
        {
            root[j] = y;
            j++;
            if(j==n+1)
                j=0;
        }
        root[tori[x]] = y;
    }
    else
    {
        tori[x] = tori[y];
        int j = tole[y];
        while(j!=tori[y])
        {
            root[j] = x;
            j++;
            if(j==n+1)
                j=0;
        }
        root[tori[y]] = x;
    }
}
void verif_debug()
{

}
int dp[105][1005][1005];///dp[i][cnt][ult]
int solve_dp()
{
    int mnm=INF;
    for(int primu=0;primu<=k;primu++)
    {
        for(int i=0;i<=k;i++)
            for(int j=0;j<=k;j++)
                dp[1][i][j]=INF;
        dp[1][primu][primu] = 0;
        for(int i=2;i<=n;i++)
        {
            for(int cnt=0;cnt<=k;cnt++)
            {
                for(int u=0;u<=cnt;u++)
                {
                    dp[i][cnt][u] = INF;
                    for(int p=0;p+u<=cnt;p++)
                    {
                        dp[i][cnt][u] = min(dp[i][cnt][u], dp[i-1][cnt-u][p] + abs((a[i]+u) - (a[i-1]+p)));
                    }
                    //if(dp[i][cnt][u]<INF) cout<<i<<" "<<cnt<<" "<<u<<"   "<<dp[i][cnt][u]<<"\n";
                }
            }
        }
        for(int cnt=0;cnt<=k;cnt++)
        {
            for(int u=0;u<=cnt;u++)
            {
                mnm = min(mnm, dp[n][cnt][u] + abs((a[n]+u) - (a[1]+primu)));
            }
        }
    }
    mnm = -mnm;
    for(int i=1;i<n;i++)
        mnm += abs(a[i]-a[i+1]);
    mnm += abs(a[1]-a[n]);
    return mnm;
}
int solve_greedy()
{
    bool bl=1;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=a[1])
            bl=0;
        if(i>1) sum += abs(a[i]-a[i-1]);
    }
    sum += abs(a[1]-a[n]);
    if(bl)
    {
        return 0;
        //cout<<0;
        //return 0;
    }
    initializeaza_secvente();

    while(!pq.empty())
    {
        verif_debug();
        int x = pq.top().second;
        pq.pop();
        //cout<<x<<" zzz\n";
        if(lun(x) > k)
            break;
        int tol = tole[x]-1;
        if(tol==0)
            tol=n;
        int tor = tori[x]+1;
        if(tor==n+1)
            tor=1;

        if(lun(x) * (min(a[root[tol]],a[root[tor]]) - a[x]) < k)
        {
            if(a[root[tol]]<a[root[tor]])
            {
                k -= lun(x) * (a[root[tol]] - a[x]);
                a[x] = a[root[tol]];
                unite(root[tol], x);
            }
            else if(a[root[tol]]>a[root[tor]])
            {
                k -= lun(x) * (a[root[tor]] - a[x]);
                a[x] = a[root[tor]];
                unite(x, root[tor]);
            }
            else
            {
                k -= lun(x) * (a[root[tor]] - a[x]);
                a[x] = a[root[tor]];
                unite(root[tol], x);
                unite(root[x], root[tor]);
            }
        }
        else
        {
            a[x] += k / lun(x);
            afis();
            break;
        }
        afis();
        bool eq=1;
        for(int i=1;i<=n;i++)
        {
            if(root[i]!=root[1])
            {
                eq=0;
                break;
            }
        }
        if(eq)
        {
            break;
        }
        ///trebuie sa verificam daca tot sirul ii egal, atunci dam break
        x = root[x];
        tol = tole[x]-1;
        if(tol==0)
            tol=n;
        tor = tori[x]+1;
        if(tor==n+1)
            tor=1;
        if(a[tol] > a[x] && a[tor] > a[x])
        {
            pq.push({-lun(x),x});
        }
    }
    for(int i=1;i<n;i++)
    {
        sum -= abs(a[root[i+1]] - a[root[i]]);
    }
    sum -= abs(a[root[n]] - a[root[1]]);
    return sum;
}
signed main()
{
    int initk;
    cin>>n>>initk;
    k=initk;
    for(int i=1;i<=n;i++)cin>>a[i];
    //cout<<solve_dp();
    cout<<solve_greedy();
    return 0;
    while(1)
    {
        for(int i=1;i<=n;i++)
        {
            inita[i] = rnd()%10;
            a[i] = inita[i];
        }
        k = initk;
        int rezdpp = solve_dp();
        int rezgreedy = solve_greedy();
        //cout<<sum;
        if(rezgreedy!=rezdpp)
        {
            //cout<<rezdpp<<" "<<rezgreedy<<"\n";
            ///do something
            for(int i=1;i<=n;i++)
            {
                cout<<inita[i]<<" ";
            }
            return 0;
        }
    }
    return 0;
}
/**
9 1000
1 1 1 2 2 3 3 1 1

9 1000
1 1 1 3 3 3 3 1 1

10 1000
5 4 3 2 1 1 2 3 4 5

8 3
7 9 1 1 9 9 9 9

n = 2 ?????

3 3
4 8 3

*/

• Subtask 1: 100 / 100