oj.uz

Submission #255150

# Submission time Handle Problem Language Result Execution time Memory
255150 2020-07-31T12:00:59 Z shayan_p Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 218 ms 34040 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[maxn];

int a[maxn];

void go(int &k, int x){
    if(k == 0){
	cout << x << " ";
	return;
    }
    if(x == 0){
	cout << x << " ";
	return;
    }
    k--;
    go(k, x-1);
    go(k, x-1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
	cin >> a[i];
    }
    a[n] = 30;
    int sm = 0;
    for(int i = 0; i < n; i++){
	sm+= 1<<a[i];
	while(__builtin_ctz(sm) < a[i+1])
	    v[i].PB(__builtin_ctz(sm)), sm+= sm & -sm, --k;
    }
    assert(k >= 0);
    for(int i = 0; i < n; i++){
	cout << a[i] << " ";
	for(int x : v[i]){
	    go(k, x);
	}
    }
    return cout << endl, 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 31864 KB Output is correct
2 Correct 145 ms 31864 KB Output is correct
3 Correct 149 ms 31864 KB Output is correct
4 Correct 146 ms 31864 KB Output is correct
5 Correct 143 ms 31992 KB Output is correct
6 Correct 155 ms 31864 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 31864 KB Output is correct
2 Correct 147 ms 31864 KB Output is correct
3 Correct 153 ms 31992 KB Output is correct
4 Correct 153 ms 31992 KB Output is correct
5 Correct 148 ms 31864 KB Output is correct
6 Correct 154 ms 31864 KB Output is correct
7 Correct 150 ms 31992 KB Output is correct
8 Correct 218 ms 31992 KB Output is correct
9 Correct 141 ms 34040 KB Output is correct
10 Correct 121 ms 30456 KB Output is correct
11 Correct 161 ms 32376 KB Output is correct
12 Correct 102 ms 25980 KB Output is correct
13 Correct 98 ms 25848 KB Output is correct
14 Correct 99 ms 25852 KB Output is correct