oj.uz

Submission #762056

# Submission time Handle Problem Language Result Execution time Memory
762056 2023-06-20T17:17:31 Z LucaIlie Zalmoxis (BOI18_zalmoxis) C++17
55 / 100
 494 ms 78280 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;
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];

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 } );
    }

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 77272 KB Output is correct
2 Correct 494 ms 78080 KB Output is correct
3 Correct 456 ms 77608 KB Output is correct
4 Correct 450 ms 77756 KB Output is correct
5 Correct 464 ms 77880 KB Output is correct
6 Correct 459 ms 76936 KB Output is correct

Subtask #2
25.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 462 ms 77524 KB Execution failed because the return code was nonzero
2 Correct 440 ms 76852 KB Output is correct
3 Runtime error 467 ms 78124 KB Execution failed because the return code was nonzero
4 Runtime error 468 ms 78096 KB Execution failed because the return code was nonzero
5 Runtime error 459 ms 77648 KB Execution failed because the return code was nonzero
6 Runtime error 471 ms 77424 KB Execution failed because the return code was nonzero
7 Runtime error 452 ms 77892 KB Execution failed because the return code was nonzero
8 Runtime error 478 ms 78280 KB Execution failed because the return code was nonzero
9 Runtime error 425 ms 69752 KB Execution failed because the return code was nonzero
10 Correct 231 ms 45128 KB Output is correct
11 Runtime error 301 ms 54912 KB Execution failed because the return code was nonzero
12 Correct 64 ms 25744 KB Output is correct
13 Correct 65 ms 25772 KB Output is correct
14 Correct 74 ms 25828 KB Output is correct