Cod sursa(job #2612307)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 8 mai 2020 20:00:08
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4 kb
/*#include<bits/stdc++.h>
#define N (int)1e5+5
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,t;
    cin>>n>>m;
    int v[n],viz[N],dp[n];
    memset(viz,0,sizeof(viz));
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;++i)
        cin>>v[i];
    dp[n-1]=1;
    viz[v[n-1]]=1;
    for(int i=n-2;i>=0;--i)
    {
        if(!viz[v[i]])
        {
            viz[v[i]]=1;
            dp[i]=dp[i+1]+1;
        }
        else
            dp[i]=dp[i+1];
    }
    for(int i=1;i<=m;++i)
    {
        cin>>t;
        cout<<dp[t-1]<<'\n';
    }

}*/
//Ksecv
/*#include<bits/stdc++.h>
#define N 100003
using namespace std;

int n,k,v[N],dp[2][N];
int s[N];

void read()
{
    ifstream fin("ksecv.in");
    fin>>n>>k;
    for(int i=0;i<n;++i)
        fin>>v[i];
    fin.close();
}


int main()
{
    read();
    bool pas=0;
    dp[0][0]=dp[0][1]=1e9;
    dp[1][0]=v[0];
    for(int j=1;j<n;++j)
    {
        dp[0][j]=1e9;
        dp[1][j]=max(dp[1][j-1],v[j]);
    }
    //cout<<dp[1][n-1];
    //dinamica in n*k
    //dp(i)(j)=min(dp(i-1)(l)+max(l+1 ... j)) dupa l de la 1 la j-1
    //i de la 1 la k
    //j de la 1 la n
    for(int i=1;i<k;++i,pas=1-pas)
    {
        for(int j=0;j<n;++j)
            dp[pas][j]=1e9;
        //stack<int> s;
        int stop=1;
        s[stop]=0;
        //in stiva imi pastrez indicii din v ai maximelor(l-ul din formula)
        //stiva va contine un sir descrescator de valori ( de fapt indicii lor )
        //fiecare valoare din stiva este un reprezentant pentru fiecare secventa
        for(int j=1;j<n;++j)
        {
            //if(stop>0)
            while(stop>0 && v[j]>=v[s[stop]])
            {
                dp[pas][j]=min(dp[pas][j],dp[1-pas][s[stop]]+v[j]);
                //daca avem o situatie de tipul:
                //  (..)(..)...(...)(...v[s[stop]]...)->urmeaza v[j] care e mai mare, trebuie actualizat numarul
                dp[pas][j]=min(dp[pas][j],dp[pas][s[stop]]-v[s[stop]]+v[j]);
                --stop;
                if(!stop)
                    break;
            }
            //daca nu e maximul pana in prezent:
            if(stop>0)
            {
                //daca incepem o noua secventa dinainte de la un indice <= s[stop]
                dp[pas][j]=min(dp[pas][j],dp[pas][s[stop]]);
                //daca incep de la s[stop]+1 (de indice mai mare am verificat mai sus
                dp[pas][j]=min(dp[pas][j],dp[1-pas][s[stop]]+v[j]);

            }

            ++stop;
            s[stop]=j;
        }

    }
    ofstream fout("ksecv.out");
    fout<<dp[k&1][n-1]<<'\n';
    fout.close();

}*/
//Order
#include<bits/stdc++.h>
using namespace std;
int st[120000];
ofstream fout("order.out");

int getMid(int s, int e)
{
    return s+(e-s)/2;
}

void build(int node,int s,int d)
{
    if(s==d)
    {
        st[node]=1;
        return;
    }
    build(2*node,s,getMid(s,d));
    build(2*node+1,getMid(s,d)+1,d);
    st[node]=st[2*node]+st[2*node+1];
    return;
}

void del(int node,int s,int d,int x)
{
    if(s==d)
    {
        fout<<s<<' ';
        st[node]=0;
        return;
    }
    //cout<<s<<' '<<d<<' '<<st[2*node]<<'\n';
    if(st[2*node]>=x)
    {
        del(2*node,s,getMid(s,d),x);
        st[node]=st[2*node]+st[2*node+1];
        return;
    }
    del(2*node+1,getMid(s,d)+1,d,x-st[2*node]);
    st[node]=st[2*node]+st[2*node+1];
    return;

}


int main()
{
    int n,k;
    ifstream fin("order.in");
    fin>>n;
    fin.close();
    k=n;
    build(1,1,n);
    int sters=2;
    for(int i=0;i<n;++i)
    {
        del(1,1,n,sters);
        --k;
        if(k>0)
        {
            sters+=i;
            //in sters imi retin al catelea 1 trebuie sters din arborele de intervale
            ++sters;
            sters%=k;
            if(!sters)
                sters=k;
            //cout<<<<sters<<' ';
        }

    }
    fout.close();
}