oj.uz

Submission #64736

# Submission time Handle Problem Language Result Execution time Memory
64736 2018-08-05T13:28:05 Z Good Zalmoxis (BOI18_zalmoxis) C++11
0 / 100
 257 ms 62884 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);
	}	
	
	for (auto i: v)
		mn = min (i, mn);	
	
	int pos = 0;
	for (int i = 1; i <= n; i++) {
		if (A[i] != v[pos]) {
			ll x = 1ll * (1 << (v[pos] - A[i]));
			x--, P[pos] = i + x;
			i += x;
		}
		else
			P[pos] = i;
				
		pos ++;
	}	
	
	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];
	}
	
	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);
		}
				
		pos = 0;
		for (int j = 0; j < v.size(); j++) {
			if (v[j] != v1[pos]) {
				ll p = 1ll * (1 << (v1[pos] - v[j]));
				p --, P[pos] = P[j + p];
				j += p;
			}
			else
				P[pos] = P[j];
			pos ++;	
		}
		
		v = v1;
		v1.clear();
	}
	
	for (int i = 1; i <= n; i++) {
		printf ("%d ", A[i]);
		
		for (auto j: E[i])
			cout << j << ' ';
	}	
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {   
                   ~~^~~~~~~~~~
zalmoxis.cpp:95: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 Incorrect 221 ms 29816 KB Unexpected end of file - int32 expected
2 Incorrect 257 ms 29816 KB Unexpected end of file - int32 expected
3 Incorrect 234 ms 29976 KB Unexpected end of file - int32 expected
4 Incorrect 235 ms 29976 KB Unexpected end of file - int32 expected
5 Incorrect 242 ms 29976 KB Unexpected end of file - int32 expected
6 Incorrect 222 ms 29976 KB Unexpected end of file - int32 expected

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 55376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 207 ms 55892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 255 ms 56104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 189 ms 56104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 169 ms 56104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 162 ms 56104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 162 ms 56104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 193 ms 56104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 180 ms 62884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 124 ms 62884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 181 ms 62884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 33 ms 62884 KB Unexpected end of file - int32 expected
13 Runtime error 55 ms 62884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 25 ms 62884 KB Unexpected end of file - int32 expected