Submission #63146

#	Time	Username	Problem	Language	Result	Execution time	Memory
63146		MatheusLealV	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	1101 ms	263168 KiB

zalmoxis

#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 (stderr)

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
• Subtask 2: 0 / 70