oj.uz

Submission #760765

# Submission time Handle Problem Language Result Execution time Memory
760765 2023-06-18T11:13:52 Z LucaIlie Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 1000 ms 76316 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[r] = l;
        rightt[l] = 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[r] = l;
        rightt[l] = r;
        value[l] = value[r] = val;
        apar[l] = apar[r] = ap;
        seg.insert( { l, r, val, ap } );
    }

    if ( k < 0 )
        return 1;

    for ( int i = 1; i <= n; i++ ) {
        cout << v[i] << " ";
        for ( int x: adaugiri[i] )
            cout << x << " ";
    }
    int val = seg.begin()->val;
    for ( int i = 0; i < k; i++ )
        cout << val + i << " ";

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 75212 KB Time limit exceeded
2 Execution timed out 1048 ms 76012 KB Time limit exceeded
3 Execution timed out 1096 ms 75644 KB Time limit exceeded
4 Execution timed out 1094 ms 75692 KB Time limit exceeded
5 Execution timed out 1077 ms 75848 KB Time limit exceeded
6 Execution timed out 1085 ms 74732 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 75556 KB Time limit exceeded
2 Execution timed out 1079 ms 74700 KB Time limit exceeded
3 Execution timed out 1095 ms 75996 KB Time limit exceeded
4 Execution timed out 1082 ms 75968 KB Time limit exceeded
5 Execution timed out 1088 ms 75648 KB Time limit exceeded
6 Execution timed out 1090 ms 75392 KB Time limit exceeded
7 Execution timed out 1086 ms 75888 KB Time limit exceeded
8 Execution timed out 1088 ms 76316 KB Time limit exceeded
9 Execution timed out 1086 ms 71640 KB Time limit exceeded
10 Execution timed out 1086 ms 62152 KB Time limit exceeded
11 Execution timed out 1078 ms 66536 KB Time limit exceeded
12 Incorrect 78 ms 30684 KB not a zalsequence
13 Incorrect 77 ms 30668 KB not a zalsequence
14 Incorrect 77 ms 30684 KB not a zalsequence