oj.uz

Submission #64746

# Submission time Handle Problem Language Result Execution time Memory
64746 2018-08-05T14:01:37 Z Good Zalmoxis (BOI18_zalmoxis) C++11
30 / 100
 1000 ms 44748 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];
	}
	
	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]);
		
		memset (cnt, 0, sizeof (cnt));
		for (auto j: E[i]) {
			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 l = j; l >= 0; l--)
				for (int h = 1; h <= cnt[l]; h++)
					printf ("%d ", l);
		}	
	}	
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:73: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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 29948 KB Output is correct
2 Correct 292 ms 30084 KB Output is correct
3 Correct 331 ms 30084 KB Output is correct
4 Correct 336 ms 30084 KB Output is correct
5 Correct 313 ms 30108 KB Output is correct
6 Correct 323 ms 30108 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 30108 KB Expected EOF
2 Incorrect 250 ms 30400 KB Expected EOF
3 Incorrect 247 ms 30692 KB Expected EOF
4 Incorrect 262 ms 30692 KB Expected EOF
5 Incorrect 263 ms 30692 KB Expected EOF
6 Incorrect 239 ms 30692 KB Expected EOF
7 Incorrect 264 ms 30692 KB Expected EOF
8 Incorrect 284 ms 30692 KB Expected EOF
9 Incorrect 418 ms 39444 KB Expected EOF
10 Incorrect 295 ms 39444 KB Expected EOF
11 Incorrect 374 ms 39444 KB Expected EOF
12 Execution timed out 1082 ms 44204 KB Time limit exceeded
13 Execution timed out 1083 ms 44748 KB Time limit exceeded
14 Execution timed out 1084 ms 44748 KB Time limit exceeded