oj.uz

Submission #762050

# Submission time Handle Problem Language Result Execution time Memory
762050 2023-06-20T16:55:18 Z LucaIlie Zalmoxis (BOI18_zalmoxis) C++17
35 / 100
 479 ms 78328 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 - k + 1 < 0 )
        return 1;
    for ( int i = 1; i < k; i++ )
        cout << val - i << " ";
    if ( k > 0 )
        cout << val - k + 1 << "\n";

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 77336 KB Output is correct
2 Correct 479 ms 78068 KB Output is correct
3 Correct 468 ms 77624 KB Output is correct
4 Correct 468 ms 77856 KB Output is correct
5 Correct 460 ms 77852 KB Output is correct
6 Correct 462 ms 76876 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 462 ms 77568 KB Execution failed because the return code was nonzero
2 Correct 456 ms 76680 KB Output is correct
3 Incorrect 473 ms 78048 KB not a zalsequence
4 Runtime error 470 ms 78156 KB Execution failed because the return code was nonzero
5 Runtime error 465 ms 77616 KB Execution failed because the return code was nonzero
6 Runtime error 477 ms 77492 KB Execution failed because the return code was nonzero
7 Runtime error 471 ms 77904 KB Execution failed because the return code was nonzero
8 Runtime error 475 ms 78328 KB Execution failed because the return code was nonzero
9 Runtime error 429 ms 69728 KB Execution failed because the return code was nonzero
10 Runtime error 203 ms 44100 KB Execution failed because the return code was nonzero
11 Runtime error 305 ms 54968 KB Execution failed because the return code was nonzero
12 Runtime error 10 ms 23764 KB Execution failed because the return code was nonzero
13 Runtime error 10 ms 23764 KB Execution failed because the return code was nonzero
14 Runtime error 10 ms 23736 KB Execution failed because the return code was nonzero