oj.uz

Submission #64766

# Submission time Handle Problem Language Result Execution time Memory
64766 2018-08-05T14:58:49 Z Good Zalmoxis (BOI18_zalmoxis) C++11
0 / 100
 432 ms 64612 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ff first
#define ss second
#define Maxn 1000003
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;

int n, k;
ll cnt[33];
int A[Maxn];
int P[Maxn];

vector <int> v, v1, E[Maxn];

int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;

	scanf ("%d%d", &n, &k);

	int mn = 40;
	for (int i = 1; i <= n; i++)
		scanf ("%d", A + i);
	
	for (int i = 1; i <= n; i++) {
		int x = A[i];
		while (v.size() > 0 and x == v.back()) {
			v.ppb();
			x++;
		}
		
		v.pb (x);
		P[v.size() - 1] = i;
	}	
	
	for (auto i: v)
		mn = min (i, mn);	
	
	ll x = 0;
	for (auto i: v) {
		ll y = i - mn;
		x += 1 << y;
	}
		
	x = (1 << (30 - mn)) - x;
	cnt[mn] = x;
	
	int sm = 0;
	for (int i = mn; i <= 30; i++) {
		cnt[i + 1] += cnt[i] / 2;
		cnt[i] %= 2;
		sm += cnt[i];
	}
	
	assert (sm < k);	
	k -= sm;
			
	for (int i = mn; i < 30; i++) {
		for (int j = 0; j < v.size(); j++) {			
			if (v[j] == i)						
				v1.pb (v[j]), E[P[j]].pb (v[j]);
				
			int e = v[j];
			while (v1.size() > 0 and e == v1.back())
				e ++, v1.ppb();
			
			v1.pb (e);
			P[v1.size() - 1] = P[j];
		}
		
		v = v1;
		v1.clear();
	}
		
	for (int i = 1; i <= n; i++) {
		printf ("%d ", A[i]);
		
		for (auto j: E[i]) {
			memset (cnt, 0, sizeof (cnt));
			cnt[j] = 1;
						
			for (int l = j; l >= 1; l--) {
				while (k > 0 and cnt[l] > 0)
					cnt[l - 1] += 2, cnt[l] --, k --;			
				
				for (int h = 1; h <= cnt[l]; h++)
					printf ("%d ", l);
			}
					
		}	
	}	
	
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {   
                   ~~^~~~~~~~~~
zalmoxis.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
  ~~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:38:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", A + i);
   ~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 188 ms 55292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 184 ms 55464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 221 ms 55516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 176 ms 55536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 197 ms 55592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 214 ms 55632 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 57708 KB Expected EOF
2 Incorrect 261 ms 57996 KB Expected EOF
3 Incorrect 320 ms 58220 KB Expected EOF
4 Incorrect 301 ms 58220 KB Expected EOF
5 Incorrect 289 ms 58220 KB Expected EOF
6 Incorrect 355 ms 58220 KB Expected EOF
7 Incorrect 276 ms 58220 KB Expected EOF
8 Incorrect 246 ms 58220 KB Expected EOF
9 Incorrect 432 ms 64612 KB Expected EOF
10 Incorrect 232 ms 64612 KB Unexpected end of file - int32 expected
11 Incorrect 263 ms 64612 KB Unexpected end of file - int32 expected
12 Incorrect 31 ms 64612 KB Unexpected end of file - int32 expected
13 Incorrect 30 ms 64612 KB Unexpected end of file - int32 expected
14 Incorrect 29 ms 64612 KB Unexpected end of file - int32 expected