Cod sursa(job #2644577)

Utilizator loraclorac lorac lorac Data 24 august 2020 23:25:26
Problema Sortare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("sortare.in");
ofstream out("sortare.out");
int a[5005],b[5005],c[5005];
int hmax[5005],val[5005];
int ans[5005];
void solve(int l,int r,int add)
{
    int dim=r-l+1;
    if(dim<1) return;
    if(dim==1) {ans[l]=add+1;return;}
    int med=l+val[dim]-1;
    solve(l,med-1,add);
    solve(med+1,r,add+val[dim]);
    ans[med]=val[dim]+add;
    if(l+b[dim]-1==med) return;
    if(l+b[dim]-1<med)
    {
        for(int i=med;i>l+b[dim]-1;--i)
            ans[i]=ans[i-1];
        ans[b[dim]]=val[dim]+add;
    }
    else
    {
        for(int i=med;i<l+b[dim]-1;++i)
            ans[i]=ans[i+1];
        ans[b[dim]]=val[dim]+add;
    }
}
int main()
{
    int n;
    in>>n;
    vector<int> srt;
    for(int i=2;i<=n;++i)
    {
        in>>a[i]>>b[i]>>c[i];
        srt.clear();
        srt.push_back(a[i]);
        srt.push_back(b[i]);
        srt.push_back(c[i]);
        sort(srt.begin(),srt.end());
        a[i]=srt[0],b[i]=srt[1],c[i]=srt[2];
    }
    hmax[1]=1;
    for(int i=2;i<=n;++i)
    {
        int rep=-1;
        if(a[i]==b[i])
            rep=a[i];
        else if(a[i]==c[i])
            rep=c[i];
        else if(b[i]==c[i])
            rep=b[i];
        if(rep!=-1)
        {
            for(int j=1;j<=i;++j)
            {
                //hmax[i]=max(hmax[i],1+max(hmax[j-1],hmax[i-j]));
                if(1+max(hmax[j-1],hmax[i-j])>hmax[i])
                {
                    val[i]=j;
                    hmax[i]=1+max(hmax[j-1],hmax[i-j]);
                }
            }
        }
        else
        {
            for(int j=2;j<i;++j)
            {
                //hmax[i]=max(hmax[i],1+max(hmax[j-1],hmax[i-j]));
                if(1+max(hmax[j-1],hmax[i-j])>hmax[i])
                {
                    val[i]=j;
                    hmax[i]=1+max(hmax[j-1],hmax[i-j]);
                }
            }
        }
    }
    out<<hmax[n]<<'\n';
    solve(1,n,0);
    for(int i=1;i<=n;++i)
        out<<ans[i]<<' ';
    return 0;
}