oj.uz

Submission #98413

# Submission time Handle Problem Language Result Execution time Memory
98413 2019-02-23T09:26:17 Z win11905 Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 470 ms 16396 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define iii tuple<int, int, int>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 1e6+5;

class zalmoxis {
private:
    int n, k, sz;
    int A[2][N];
    bool state[2][N];
    vector<int> vec;
    void build(int dep, int l, int r) {
        if(l == r) return void(vec.emplace_back(dep));
        int m = l + r >>1;
        build(dep-1, l, m), build(dep-1, m+1, r);
    }
public:
    void solve(istream& cin, ostream& cout) {
        cin >> n >> k;
        sz = n;
        for(int i = 0; i < sz; ++i) {
            cin >> A[0][i];
            state[0][i] = true;
        }
        for(int i = 0; i < 30; ++i) {
            int sum = 0, pos = 0;
            bool st = false;
            for(int j = 0; j < sz; ++j) {
                if(A[i&1][j] <= i) sum += 1 << A[i&1][j];
                else if(sum) {
                    assert(sum == 1 << i);
                    A[~i&1][pos] = i, state[~i&1][pos] = false, sum += 1 << i;
                    pos++;
                }
                A[~i&1][pos] = A[i&1][j], state[~i&1][pos] = state[i&1][j];
                pos++;
                if(sum == 1 << (i+1)) sum = 0;
            }
            if(sum) {
                assert(sum == 1 << i);
                A[~i&1][pos] = i, state[~i&1][pos] = false, sum += 1 << i;
                pos++;
            }
            sz = pos;
        }
        int mx = 0, pos = 0;
        for(int j = 0; j < sz; ++j) if(!state[0][j] && mx < A[0][j]) mx = A[0][j], pos = j;
        int reach = n+k - sz + 1;
        for(int j = 0; j < sz; ++j) {
            if(j != pos) cout << A[0][j] << ' ';
            else {
                build(A[0][j], 1, reach);
                for(auto x : vec) cout << x << ' ';
            }
        }
        cout << endl;
//        for(int j = 0; j < sz; ++j) cerr << A[0][j] << ' ';
//        cerr << endl;
//        for(int j = 0; j < sz; ++j) cerr << state[0][j] << "  ";
//        cerr << endl;
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        zalmoxis *obj = new zalmoxis();
        obj->solve(in, out);
    }
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Compilation message

zalmoxis.cpp: In member function 'void zalmoxis::build(int, int, int)':
zalmoxis.cpp:31:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >>1;
                 ~~^~~
zalmoxis.cpp: In member function 'void zalmoxis::solve(std::istream&, std::ostream&)':
zalmoxis.cpp:44:18: warning: unused variable 'st' [-Wunused-variable]
             bool st = false;
                  ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 14200 KB Output is correct
2 Correct 470 ms 14328 KB Output is correct
3 Correct 329 ms 14404 KB Output is correct
4 Correct 338 ms 14200 KB Output is correct
5 Correct 289 ms 14424 KB Output is correct
6 Correct 285 ms 14332 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 14368 KB Output is correct
2 Correct 217 ms 14200 KB Output is correct
3 Correct 255 ms 14324 KB Output is correct
4 Correct 272 ms 14364 KB Output is correct
5 Correct 354 ms 14356 KB Output is correct
6 Correct 258 ms 14200 KB Output is correct
7 Correct 215 ms 14200 KB Output is correct
8 Correct 363 ms 14340 KB Output is correct
9 Correct 257 ms 14420 KB Output is correct
10 Correct 157 ms 15980 KB Output is correct
11 Correct 261 ms 14828 KB Output is correct
12 Correct 139 ms 16232 KB Output is correct
13 Correct 107 ms 16224 KB Output is correct
14 Correct 106 ms 16396 KB Output is correct