Submission #762081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
762081	2023-06-20T18:36:33 Z	LucaIlie	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	520 ms	102704 KB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

struct xxx {
    int l, r, val, ap;

    bool operator<( const xxx &x ) const {
        if ( val == x.val )
            return l < x.l;
        return val < x.val;
    }
};

const int MAX_N = 1e6;
bool del[MAX_N + 2], original[MAX_N + 1];
int v[MAX_N + 2], leftt[MAX_N + 2], rightt[MAX_N + 2], value[MAX_N + 2], apar[MAX_N + 2];
set <xxx> seg;
vector <int> adaugiri[MAX_N + 1], tba[MAX_N + 1];

int main() {
    int n, k;

    cin >> n >> k;
    for ( int i = 1; i <= n; i++ )
        cin >> v[i];

    int l = 1, r = 1;
    while ( l <= n ) {
        r = l;
        while ( r + 1 <= n && v[l] == v[r + 1] )
            r++;
        leftt[l] = leftt[r] = l;
        rightt[l] = rightt[r] = r;
        value[l] = value[r] = v[l];
        apar[l] = apar[r] = r - l + 1;
        seg.insert( { l, r, v[l], r - l + 1 } );
        l = r + 1;
    }

    value[0] = value[n + 1] = -1;
    while ( !(seg.size() == 1 && seg.begin()->ap == 1) ) {
        int l = seg.begin()->l, r = seg.begin()->r, val = seg.begin()->val, ap = seg.begin()->ap;
        seg.erase( { l, r, val, ap } );

        if ( ap % 2 == 1 ) {
            ap++;
            k--;
            adaugiri[r].push_back( val );
        }
        ap /= 2;
        val++;

        if ( val == value[l - 1] ) {
            ap += apar[l - 1];
            seg.erase( { leftt[l - 1], rightt[l - 1], value[l - 1], apar[l - 1] } );
            l = leftt[l - 1];
        }
        if ( val == value[r + 1] ) {
            ap += apar[r + 1];
            seg.erase( { leftt[r + 1], rightt[r + 1], value[r + 1], apar[r + 1] } );
            r = rightt[r + 1];
        }

        leftt[l] = leftt[r] = l;
        rightt[l] = rightt[r] = r;
        value[l] = value[r] = val;
        apar[l] = apar[r] = ap;
        seg.insert( { l, r, val, ap } );
    }

    int val = seg.begin()->val;
    if ( !(val == 30 && k > 0) ) {
        for ( int i = 1; i <= n; i++ ) {
            cout << v[i] << " ";
            for ( int x: adaugiri[i] )
                cout << x << " ";
        }

        for ( ; val < 29; val++ ) {
            cout << val << " ";
            k--;
        }
        for ( int b = 19; b >= 0; b-- ) {
            if ( k >= (1 << b) ) {
                k -= (1 << b);
                if ( k > 0 )
                    val--;
                for ( int i = 0; i < (1 << b); i++ )
                    cout << val - b << " ";
            }
        }

        return 0;
    }

    vector <int> aux;
    for ( int i = 1; i <= n; i++ ) {
        original[aux.size()] = true;
        aux.push_back( v[i] );
        for ( int x: adaugiri[i] )
            aux.push_back( x );
    }
    n = aux.size();
    for ( int i = 0; i < n; i++ ) {
        v[i] = aux[i];
        adaugiri[i].clear();
    }

    for ( int b = 0; b < 1; b++ ) {
        for ( int i = 0; i < n; i++ ) {
            if ( k == 0 || original[i] )
                continue;
            int x = v[i];

            int c = log2( k + 1 );
            c = min( c, x );
            for ( int j = 0; j < (1 << c); j++ )
                adaugiri[i].push_back( x - c );
            del[i] = true;
            k -= (1 << c) - 1;
        }

        aux.clear();
        for ( int i = 0; i < n; i++ ) {
            if ( del[i] ) {
                del[i] = false;
                for ( int x: adaugiri[i] )
                    aux.push_back( x );
            }
            else {
                original[aux.size()] = original[i];
                aux.push_back( v[i] );
            }
        }
        n = aux.size();
        for ( int i = 0; i < n; i++ ) {
            v[i] = aux[i];
            adaugiri[i].clear();
        }
    }

    for ( int i = 0; i < n; i++ )
        cout << v[i] << " ";

    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	459 ms	100744 KB	Output is correct
2	Correct	481 ms	101588 KB	Output is correct
3	Correct	472 ms	101144 KB	Output is correct
4	Correct	476 ms	101272 KB	Output is correct
5	Correct	475 ms	101388 KB	Output is correct
6	Correct	461 ms	100300 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	520 ms	102028 KB	Output is correct
2	Correct	461 ms	100264 KB	Output is correct
3	Correct	497 ms	102588 KB	Output is correct
4	Correct	482 ms	102612 KB	Output is correct
5	Correct	482 ms	102088 KB	Output is correct
6	Correct	472 ms	101988 KB	Output is correct
7	Correct	490 ms	102440 KB	Output is correct
8	Correct	496 ms	102704 KB	Output is correct
9	Correct	459 ms	99120 KB	Output is correct
10	Correct	241 ms	68552 KB	Output is correct
11	Correct	402 ms	86640 KB	Output is correct
12	Correct	79 ms	49232 KB	Output is correct
13	Correct	73 ms	49232 KB	Output is correct
14	Correct	78 ms	49208 KB	Output is correct