oj.uz

답안 #255173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255173 2020-07-31T13:38:31 Z amoo_safar Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 975 ms 262148 KB 
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

vector<pll> nw, fut, All;
vector<ll> Ans;

void Ins(ll num, ll cnt){
	if(cnt == 1){
		Ans.pb(num);
		return ;
	}
	Ins(num - 1, cnt / 2);
	Ins(num - 1, (cnt + 1) / 2);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, k;
	cin >> n >> k;
	ll v;
	for(int i = 1; i <= n; i++){
		cin >> v;
		All.pb({v, i * (k + 2)});
		nw.pb({v, i * (k + 2)});
	}
	ll rq = k;
	int m;
	for(int lg = 0; lg < 30; lg++){
		fut.clear();
		m = nw.size();
		for(int i = 0; i < m; i++){
			if(nw[i].F != lg){
				fut.pb(nw[i]);
				continue;
			}
			if((i + 1 < m) && (nw[i + 1].F == lg)){
				fut.pb({nw[i + 1].F + 1, nw[i + 1].S});
				i ++;
				continue;
			}
			fut.pb({nw[i].F + 1, nw[i].S + 1});
			All.pb({nw[i].F, nw[i].S + 1});
			rq --;
		}
		swap(nw, fut);
	}

	sort(all(All), [&](pll A, pll B){
		return A.S < B.S;
	});
	for(auto X : All){
		if(X.S % (k + 2) == 0){
			Ans.pb(X.F);
			continue;
		}
		ll d = min(rq, (1ll << X.F) - 1);
		Ins(X.F, d + 1);
	}
	for(auto x : Ans) cout << x << ' ';
	cout << '\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 65380 KB Output is correct
2 Correct 286 ms 65628 KB Output is correct
3 Correct 278 ms 65652 KB Output is correct
4 Correct 269 ms 65504 KB Output is correct
5 Correct 261 ms 65640 KB Output is correct
6 Correct 271 ms 65236 KB Output is correct

Subtask #2
5.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 384 ms 65384 KB Expected EOF
2 Correct 315 ms 65128 KB Output is correct
3 Incorrect 362 ms 65636 KB Expected EOF
4 Incorrect 263 ms 65892 KB Expected EOF
5 Incorrect 347 ms 65640 KB Expected EOF
6 Incorrect 266 ms 65372 KB Expected EOF
7 Incorrect 261 ms 65628 KB Expected EOF
8 Incorrect 393 ms 65896 KB Expected EOF
9 Runtime error 473 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 359 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 425 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Incorrect 969 ms 131928 KB Expected EOF
13 Incorrect 975 ms 131804 KB Expected EOF
14 Incorrect 963 ms 131800 KB Expected EOF