oj.uz

Submission #762076

# Submission time Handle Problem Language Result Execution time Memory
762076 2023-06-20T17:57:35 Z LucaIlie Zalmoxis (BOI18_zalmoxis) C++17
60 / 100
 617 ms 101744 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 = 19; 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 452 ms 100748 KB Output is correct
2 Correct 470 ms 101580 KB Output is correct
3 Correct 465 ms 101224 KB Output is correct
4 Correct 467 ms 101304 KB Output is correct
5 Correct 452 ms 101444 KB Output is correct
6 Correct 447 ms 100444 KB Output is correct

Subtask #2
30.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 582 ms 101092 KB Expected EOF
2 Correct 442 ms 100220 KB Output is correct
3 Incorrect 591 ms 101552 KB Expected EOF
4 Correct 602 ms 101584 KB Output is correct
5 Incorrect 576 ms 101184 KB Expected EOF
6 Incorrect 585 ms 100960 KB Expected EOF
7 Incorrect 589 ms 101436 KB Expected EOF
8 Incorrect 606 ms 101744 KB Expected EOF
9 Incorrect 617 ms 93588 KB Expected EOF
10 Correct 235 ms 68656 KB Output is correct
11 Incorrect 476 ms 81472 KB Expected EOF
12 Correct 74 ms 49228 KB Output is correct
13 Correct 75 ms 49252 KB Output is correct
14 Correct 79 ms 49232 KB Output is correct