oj.uz

Submission #63147

# Submission time Handle Problem Language Result Execution time Memory
63147 2018-08-01T01:12:28 Z MatheusLealV Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 1000 ms 263168 KB 
#include <bits/stdc++.h>
#define N 1000050
#define f first
#define s second
using namespace std;

int n, k, v[N], dir[N], esq[N], id, original[N];

vector<int> add;

inline void erase(int p)
{
	// cout<<"REMOVE "<<p<<"\n";
	// cout<<"DIR [ "<<esq[p]<<" ]  = "<<dir[p]<<"\n";

	dir[esq[p]] = dir[p];

	// cout<<"ESQ[ "<<dir[p]<<" ]  = "<<esq[p]<<"\n";

	esq[dir[p]] = esq[p];
}

vector<int> ans[N];

int soma = 0, ini[N];

inline void insert(int p, int val) // criar uma posicao a direita de "p"
{
	++id;

	dir[id] = dir[p];

	esq[id] = p;

	esq[ dir[p] ] = id;

	dir[p] = id;

	v[id] = val;

	original[id] = original[p];

	ans[ original[p] ].push_back(val);

	soma ++;

	//cout<<original[p]<<" ADICIONA "<<dir[id]<<" "<<val<<"\n";
}

inline void print()
{
	int x = dir[0];

	while(x <= id)
	{
		cout<<v[x]<<" ";

		x = dir[x];
	}

	cout<<"\n";
}

inline int rebuild()
{
	int x = dir[0], cnt = 0;

	while(x <= id)
	{		
		int y = dir[x];

		if(v[x] == v[y])
		{
			v[x] ++;

			erase(y);

			original[x] = max(original[x], original[y]);

			cnt ++;
		}

		x = y;
	}

	return cnt;
}

inline void complete(int x)
{
	//return;
	int p = dir[0], cnt = 0;

	while(p <= id)
	{
		int y = dir[p];

		//cout<<"POS "<<p<<" "<<id<<"\n";

		if(v[p] == x) {
			insert(p, x);
		}

		p = y;
	}

	//cout<<"FIM\n";
}

inline void merge()
{
	rebuild();
	/*while(true) {
		if(!rebuild()) break;
	}*/
}

vector<int> resp;

inline void decompe(int x)
{
	if(!soma or x == 0)
	{
		resp.push_back(x);

		return;
	}

	soma --;

	decompe(x - 1), decompe(x - 1);	
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>k;

	id = n;

	dir[0] = 1;

	for(int i = 1; i <= n; i++)
	{
		cin>>v[i];

		ini[i] = v[i];

		original[i] = i;

		dir[i] = i + 1;

		esq[i] = i - 1;
	}

	dir[n] = N;

	for(int x = 1; x <= 30; x++)
	{
		merge();

		if(x < 30) complete(x);
	}

	soma = k - soma;

	//cout<<"SOMAAA "<<soma<<"\n";
	
	for(int i = 1; i <= n; i++)
	{
		resp.push_back(ini[i]);

		for(auto x: ans[i])
		{
			decompe(x);
		}
	}

	for(auto x: resp) cout<<x<<" ";

	cout<<"\n";
}

Compilation message

zalmoxis.cpp: In function 'void complete(int)':
zalmoxis.cpp:92:18: warning: unused variable 'cnt' [-Wunused-variable]
  int p = dir[0], cnt = 0;
                  ^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 263168 KB Time limit exceeded
2 Execution timed out 1088 ms 263168 KB Time limit exceeded
3 Execution timed out 1066 ms 263168 KB Time limit exceeded
4 Execution timed out 1088 ms 263168 KB Time limit exceeded
5 Execution timed out 1101 ms 263168 KB Time limit exceeded
6 Execution timed out 1058 ms 263168 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 263168 KB Time limit exceeded
2 Execution timed out 1110 ms 263168 KB Time limit exceeded
3 Execution timed out 1070 ms 263168 KB Time limit exceeded
4 Execution timed out 1088 ms 263168 KB Time limit exceeded
5 Execution timed out 1071 ms 263168 KB Time limit exceeded
6 Execution timed out 1037 ms 263168 KB Time limit exceeded
7 Execution timed out 1039 ms 263168 KB Time limit exceeded
8 Execution timed out 1044 ms 263168 KB Time limit exceeded
9 Execution timed out 1031 ms 263168 KB Time limit exceeded
10 Runtime error 290 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
11 Execution timed out 1093 ms 263168 KB Time limit exceeded
12 Runtime error 111 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
13 Runtime error 108 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
14 Runtime error 130 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.