oj.uz

답안 #762081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
762081 2023-06-20T18:36:33 Z LucaIlie Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 520 ms 102704 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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