oj.uz

Submission #302589

# Submission time Handle Problem Language Result Execution time Memory
302589 2020-09-18T20:52:59 Z brkdnmz Zalmoxis (BOI18_zalmoxis) C++17
35 / 100
 1000 ms 37416 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);
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		cin>>ar[i];
	}
	dfs();
	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;
			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 156 ms 10744 KB Output is correct
2 Correct 159 ms 10616 KB Output is correct
3 Correct 156 ms 10616 KB Output is correct
4 Correct 160 ms 10700 KB Output is correct
5 Correct 156 ms 10744 KB Output is correct
6 Correct 157 ms 10656 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 12280 KB Expected EOF
2 Correct 159 ms 13304 KB Output is correct
3 Incorrect 162 ms 13432 KB Expected EOF
4 Incorrect 162 ms 12408 KB Expected EOF
5 Incorrect 159 ms 12408 KB Expected EOF
6 Incorrect 167 ms 12408 KB Expected EOF
7 Incorrect 166 ms 12280 KB Expected EOF
8 Incorrect 157 ms 12408 KB Expected EOF
9 Execution timed out 1073 ms 37416 KB Time limit exceeded
10 Execution timed out 1088 ms 33424 KB Time limit exceeded
11 Execution timed out 1088 ms 34704 KB Time limit exceeded
12 Incorrect 857 ms 22612 KB Expected EOF
13 Incorrect 814 ms 22596 KB Expected EOF
14 Incorrect 796 ms 22836 KB Expected EOF