oj.uz

Submission #63146

# Submission time Handle Problem Language Result Execution time Memory
63146 2018-08-01T01:10:33 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;

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];

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";
}

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

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

		x = dir[x];
	}

	cout<<"\n";
}

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;
}

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";
}

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

vector<int> resp;

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 1074 ms 263168 KB Time limit exceeded
2 Execution timed out 1081 ms 263168 KB Time limit exceeded
3 Execution timed out 1090 ms 263168 KB Time limit exceeded
4 Execution timed out 1100 ms 263168 KB Time limit exceeded
5 Execution timed out 1088 ms 263168 KB Time limit exceeded
6 Execution timed out 1081 ms 263168 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 263168 KB Time limit exceeded
2 Execution timed out 1099 ms 263168 KB Time limit exceeded
3 Execution timed out 1101 ms 263168 KB Time limit exceeded
4 Execution timed out 1048 ms 263168 KB Time limit exceeded
5 Execution timed out 1070 ms 263168 KB Time limit exceeded
6 Execution timed out 1096 ms 263168 KB Time limit exceeded
7 Execution timed out 1095 ms 263168 KB Time limit exceeded
8 Execution timed out 1078 ms 263168 KB Time limit exceeded
9 Execution timed out 1101 ms 263168 KB Time limit exceeded
10 Runtime error 352 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 Runtime error 337 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.
12 Runtime error 101 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 127 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 121 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.