oj.uz

Submission #977632

# Submission time Handle Problem Language Result Execution time Memory
977632 2024-05-08T07:56:17 Z alexdd Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 275 ms 93392 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])
            {
                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;
            }
        }
    }
    int cur=1;
    for(int i=1;i<=n;i++)
    {
        if(cur<=initn) aux.push_back(inita[cur]);
        else calc(inita[cur]);
        cur = nxt[cur][1];
    }
    for(auto x:aux)
        cout<<x<<" ";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 92488 KB Output is correct
2 Correct 275 ms 92608 KB Output is correct
3 Correct 263 ms 92948 KB Output is correct
4 Correct 259 ms 92640 KB Output is correct
5 Correct 252 ms 93060 KB Output is correct
6 Correct 255 ms 93256 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 92188 KB Output is correct
2 Correct 256 ms 93392 KB Output is correct
3 Correct 268 ms 90572 KB Output is correct
4 Correct 268 ms 92616 KB Output is correct
5 Correct 262 ms 93068 KB Output is correct
6 Correct 268 ms 92860 KB Output is correct
7 Correct 267 ms 92840 KB Output is correct
8 Correct 262 ms 92484 KB Output is correct
9 Correct 235 ms 82556 KB Output is correct
10 Correct 120 ms 50596 KB Output is correct
11 Correct 171 ms 63880 KB Output is correct
12 Correct 58 ms 18416 KB Output is correct
13 Correct 56 ms 18896 KB Output is correct
14 Correct 73 ms 18616 KB Output is correct