oj.uz

Submission #762077

# Submission time Handle Problem Language Result Execution time Memory
762077 2023-06-20T18:00:55 Z LucaIlie Zalmoxis (BOI18_zalmoxis) C++17
55 / 100
 1000 ms 101552 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];
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;
    }

    for ( int b = 100; b >= 0; b-- ) {
        for ( int i = 1; i <= n; i++ ) {
            for ( int l = 0; l < adaugiri[i].size(); l++ ) {
                if ( k == 0 )
                    continue;
                int x = adaugiri[i][l];

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

        for ( int i = 1; i <= n; i++ ) {
            int j = 0;
            for ( int l = 0; l < adaugiri[i].size(); l++ ) {
                if ( del[l] )
                    del[l] = false;
                else
                    adaugiri[i][j++] = adaugiri[i][l];
            }
            adaugiri[i].resize( j );
        }

        for ( int i = 1; i <= n; i++ ) {
            for ( int x: tba[i] )
                adaugiri[i].push_back( x );
            tba[i].clear();
        }
    }

    for ( int i = 1; i <= n; i++ ) {
        cout << v[i] << " ";
        for ( int x: adaugiri[i] )
            cout << x << " ";
    }

    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:99:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for ( int l = 0; l < adaugiri[i].size(); l++ ) {
      |                              ~~^~~~~~~~~~~~~~~~~~~~
zalmoxis.cpp:115:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for ( int l = 0; l < adaugiri[i].size(); l++ ) {
      |                              ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 100736 KB Output is correct
2 Correct 491 ms 101552 KB Output is correct
3 Correct 479 ms 101064 KB Output is correct
4 Correct 506 ms 101320 KB Output is correct
5 Correct 473 ms 101376 KB Output is correct
6 Correct 471 ms 100392 KB Output is correct

Subtask #2
25.0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 98912 KB Time limit exceeded
2 Correct 477 ms 100328 KB Output is correct
3 Execution timed out 1073 ms 99464 KB Time limit exceeded
4 Execution timed out 1090 ms 99528 KB Time limit exceeded
5 Execution timed out 1072 ms 99016 KB Time limit exceeded
6 Execution timed out 1081 ms 98892 KB Time limit exceeded
7 Execution timed out 1087 ms 99324 KB Time limit exceeded
8 Execution timed out 1090 ms 99688 KB Time limit exceeded
9 Execution timed out 1091 ms 91540 KB Time limit exceeded
10 Correct 252 ms 68616 KB Output is correct
11 Execution timed out 1101 ms 81476 KB Time limit exceeded
12 Correct 78 ms 49228 KB Output is correct
13 Correct 77 ms 49280 KB Output is correct
14 Correct 75 ms 49236 KB Output is correct