oj.uz

Submission #302600

# Submission time Handle Problem Language Result Execution time Memory
302600 2020-09-18T21:03:22 Z brkdnmz Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 178 ms 11308 KB 
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <iomanip>
#include <cassert>
#include <random>
using namespace std;

#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define FOR(i, n) for(int i = 0; i < (n); i++)
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

const int mod = 1e9 + 7;
const int mod2 = 998244353;

void fact_init(int n);
ll exp(ll taban, ll us, ll md);
ll ebob(ll a, ll b);
ll ekok(ll a, ll b);
ll komb(ll a, ll b);

vector<ll> fact;
vector<ll> inv_fact;
void fact_init(int n){
    fact.resize(n+5);
    inv_fact.resize(n+5);
    fact[0] = inv_fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = (fact[i-1] * i) % mod;
        inv_fact[i] = exp(fact[i], mod-2, mod);
    }
}
ll exp(ll taban, ll us, ll md) {
    ll carpan = taban % md;
    if(carpan == 0) return 0;
    ll temp = us;
    ll res = 1;
    while(temp){
        if(temp % 2) res = (res*carpan) % md;
        temp /= 2;
        carpan = (carpan*carpan) % md;
    }
    return res;
}
 
ll ebob(ll a, ll b){
    if(!a)return b;
    return ebob(b%a, a);
}

ll ekok(ll a, ll b){
    return (a*b)/ebob(a, b);
}

ll komb(ll a, ll b){
    if(a < b) return 0;
    return fact[a] * (inv_fact[a-b] * inv_fact[b] % mod) % mod;
}
const int N = 1e6 + 5;
int ar[N];
int ptr = 0;
int ptr2 = 0;
int n;
int k;
int print_order[2*N];
bool special[2*N];
void dfs(int cur = 30, int num = 1, bool yon = 0){
	if(ptr < n && cur == ar[ptr]){
		print_order[ptr2++] = cur;
		ptr++;
		return;
	}else if((ptr < n && cur < ar[ptr]) || ptr == n){
		if(!yon) return;
		special[ptr2] = true;
		print_order[ptr2++] = cur;
		k--;
		return;
	}
	dfs(cur-1, 2*num, 0);
	dfs(cur-1, 2*num+1, 1);
	return;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
	//n = 1, k = 2*524288;
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		//ar[i] = 0;
		cin>>ar[i];
	}
	dfs();
	assert(ptr == n);
	assert(ptr2 <= N);
	for(int i = 0; i < ptr2; i++){
		if(!special[i]) cout<<print_order[i]<<" ";
		else{
			int cur = print_order[i];
			int cnt = 1;
			while(2*cnt - 1 <= k && cur){
				cur--;
				cnt *= 2;
			}
			int cnt2 = 0;
			if(cur){ //which means 2*cnt - 1 > k
				cnt2 = k - (cnt-1);
				cnt -= cnt2;
			}
			cnt2 *= 2;
			k -= cnt + cnt2 - 1;
			while(cnt--) cout<<cur<<" ";
			while(cnt2--) cout<<cur-1<<" ";
		}
	}
	cout<<"\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 10360 KB Output is correct
2 Correct 161 ms 10232 KB Output is correct
3 Correct 154 ms 10232 KB Output is correct
4 Correct 158 ms 10232 KB Output is correct
5 Correct 157 ms 10232 KB Output is correct
6 Correct 153 ms 10216 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 10232 KB Output is correct
2 Correct 178 ms 11308 KB Output is correct
3 Correct 157 ms 11256 KB Output is correct
4 Correct 154 ms 10360 KB Output is correct
5 Correct 153 ms 10360 KB Output is correct
6 Correct 159 ms 10276 KB Output is correct
7 Correct 163 ms 10232 KB Output is correct
8 Correct 156 ms 10360 KB Output is correct
9 Correct 150 ms 10220 KB Output is correct
10 Correct 102 ms 5752 KB Output is correct
11 Correct 124 ms 7672 KB Output is correct
12 Correct 74 ms 2424 KB Output is correct
13 Correct 72 ms 2388 KB Output is correct
14 Correct 74 ms 2424 KB Output is correct