oj.uz

Submission #762078

# Submission time Handle Problem Language Result Execution time Memory
762078 2023-06-20T18:01:32 Z LucaIlie Zalmoxis (BOI18_zalmoxis) C++17
60 / 100
 943 ms 101844 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 = 50; 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 472 ms 100780 KB Output is correct
2 Correct 485 ms 101556 KB Output is correct
3 Correct 482 ms 101104 KB Output is correct
4 Correct 483 ms 101284 KB Output is correct
5 Correct 485 ms 101380 KB Output is correct
6 Correct 508 ms 100284 KB Output is correct

Subtask #2
30.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 849 ms 101112 KB Expected EOF
2 Correct 486 ms 100224 KB Output is correct
3 Incorrect 837 ms 101672 KB Expected EOF
4 Correct 858 ms 101604 KB Output is correct
5 Incorrect 822 ms 101188 KB Expected EOF
6 Incorrect 856 ms 100964 KB Expected EOF
7 Incorrect 840 ms 101412 KB Expected EOF
8 Incorrect 833 ms 101844 KB Expected EOF
9 Incorrect 943 ms 93660 KB Expected EOF
10 Correct 283 ms 68664 KB Output is correct
11 Incorrect 737 ms 81472 KB Expected EOF
12 Correct 75 ms 49216 KB Output is correct
13 Correct 76 ms 49264 KB Output is correct
14 Correct 75 ms 49288 KB Output is correct