oj.uz

Submission #977630

# Submission time Handle Problem Language Result Execution time Memory
977630 2024-05-08T07:55:24 Z alexdd Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 322 ms 95748 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,cnt;
set<pair<int,int>> rez;
vector<int> pozs[31];
int a[2000005],inita[2000005];
int nxt[2000005][2],prec[2000005][2];
int tori[2000005];
void baga_dupa(int p, int x, int c)
{
    int pnxt = nxt[p][c];
    nxt[p][c] = x;
    nxt[x][c] = pnxt;

    prec[x][c] = p;
    prec[pnxt][c] = x;
}
void scoate(int p, int c)
{
    nxt[prec[p][c]][c] = nxt[p][c];
    prec[nxt[p][c]][c] = prec[p][c];
}
vector<int> aux;
void calc(int x)
{
    if(k<=0 || x==0)
    {
        aux.push_back(x);
        return;
    }
    k--;
    calc(x-1);
    calc(x-1);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    int initn=n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        inita[i]=a[i];
        prec[i][0]=prec[i][1]=i-1;
        nxt[i][0]=nxt[i][1]=i+1;
        pozs[a[i]].push_back(i);
        tori[i]=i;
    }
    nxt[n][0]=nxt[n][1]=0;
    for(int i=0;i<30;i++)
    {
        sort(pozs[i].begin(),pozs[i].end());
        for(auto x:pozs[i])
        {
            assert(x<=initn);
        }
        for(int j=(int)pozs[i].size()-1;j>=0;j--)
        {
            if(j>0 && nxt[pozs[i][j-1]][0] == pozs[i][j] && prec[pozs[i][j]][0] == pozs[i][j-1])
            {
                //cout<<i<<" zzz\n";
                pozs[i+1].push_back(pozs[i][j]);

                a[pozs[i][j]]++;
                scoate(pozs[i][j-1],0);
                j--;
            }
            else
            {
                pozs[i+1].push_back(pozs[i][j]);

                k--;
                n++;
                a[n]=inita[n]=i;
                baga_dupa(tori[pozs[i][j]],n,1);
                a[pozs[i][j]]++;
                tori[pozs[i][j]]=n;
            }
        }
        /*cout<<i<<"    ";
        int cur=1;
        while(cur!=0)
        {
            cout<<a[cur]<<" ";
            cur = nxt[cur][0];
        }
        cout<<"\n";*/
    }
    assert(k>=0);
    assert((int)pozs[30].size()==1);
    assert(n<=2000000);
    int primu=-1;
    for(int i=1;i<=n;i++)
        if(prec[i][1]==0)
            primu=i;
    assert(primu!=-1);
    int cur=primu;
    for(int i=1;i<=n;i++)
    {
        if(cur<=initn) aux.push_back(inita[cur]);
        else calc(inita[cur]);
        cur = nxt[cur][1];
    }
    assert(k==0);
    for(auto x:aux)
        cout<<x<<" ";
    return 0;
}
/**
5 1
29 27 25 25 28

1 5
29


9 0
28 28 25 25 26 25 25 26 28

8 1
28 25 25 26 25 25 26 28

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 94664 KB Output is correct
2 Correct 264 ms 94620 KB Output is correct
3 Correct 264 ms 94728 KB Output is correct
4 Correct 296 ms 94520 KB Output is correct
5 Correct 274 ms 94928 KB Output is correct
6 Correct 264 ms 95348 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 94436 KB Output is correct
2 Correct 255 ms 95748 KB Output is correct
3 Correct 264 ms 92500 KB Output is correct
4 Correct 267 ms 94668 KB Output is correct
5 Correct 268 ms 95332 KB Output is correct
6 Correct 262 ms 94480 KB Output is correct
7 Correct 271 ms 95036 KB Output is correct
8 Correct 265 ms 94824 KB Output is correct
9 Correct 234 ms 84824 KB Output is correct
10 Correct 139 ms 50984 KB Output is correct
11 Correct 169 ms 64904 KB Output is correct
12 Correct 58 ms 18616 KB Output is correct
13 Correct 55 ms 18896 KB Output is correct
14 Correct 51 ms 18592 KB Output is correct