Submission #81804

#	Time	Username	Problem	Language	Result	Execution time	Memory
81804		Plurm	Zalmoxis (BOI18_zalmoxis)	C++11	0 / 100	1095 ms	141712 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;
int gt;
class node{
public:
	node* l;
	node* r;
	node* lnk;
	int key;
	int t;
	node(int x = -1){
		t = ++gt;
		key = x;
		l = r = lnk = NULL;
	}
};
node* ans;
node* ansb;
class Compare{
public:
	const bool operator()(node* x,node* y){
		return x->key < y->key ? true : x->key == y->key ? x->t < y->t : false;
	}
};
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	set<node*, Compare> ms;
	ans = new node(-1); // Head
	ansb = ans;
	for(int i = 0; i < n; i++){
		int cur;
		scanf("%d",&cur);
		ansb->r = new node(cur);
		ansb->r->l = ansb;
		if(ansb->lnk) ansb->lnk->r = ansb->r;
		ansb = ansb->r;
		ansb->lnk = new node(cur);
		ansb->lnk->l = ansb->l;
		ms.insert(ansb->lnk);
	}
	ansb->r = new node(-1);
	ansb->r->l = ansb;
	if(ansb->lnk) ansb->lnk->r = ansb->r;
	ansb = ansb->r;
	set<node*> v;
	while((*ms.begin())->key < 30){
		auto cur = *ms.begin();
		bool collapsing = false;
		if(cur->r != ansb && cur->r->lnk->key == cur->key){
			ms.erase(cur);
			collapsing = true;
			ms.erase(cur->r->lnk);
			auto buf = cur->r->lnk->r;
			delete cur->r->lnk;
			cur->r->lnk = cur;
			cur->r = buf;
			cur->key++;
			ms.insert(cur);
		}else if(cur->l != ans && cur->l->lnk->key == cur->key){
			ms.erase(cur);
			collapsing = true;
			ms.erase(cur->l->lnk);
			auto buf = cur->l->lnk->l;
			delete cur->l->lnk;
			cur->l->lnk = cur;
			cur->l = buf;
			cur->key++;
			ms.insert(cur);
		}
		if(collapsing) continue;
		cur->l->r->r->l = new node(cur->l->r->key);
		v.insert(cur->l->r->r->l);
		cur->l->r->r->l->r = cur->l->r->r;
		cur->l->r->r->l->l = cur->l->r;
		cur->l->r->r = cur->l->r->r->l;
		cur->l->r->key = cur->key;
		cur->l->r->r->lnk = new node(cur->key);
		ms.insert(cur->l->r->r->lnk);
		cur->l->r->r->lnk->l = cur->l->r;
		cur->l->r->r->lnk->r = cur->r;
		cur->r = cur->l->r->r;
	}
	node* cur = ans->r;
	int cnt = v.size();
	while(cur != ansb){
		if(v.find(cur) != v.end()){
			while(cnt < k && cur->key > 1){
				cur->r->l = new node(cur->key-1);
				cur->r->l->r = cur->r;
				cur->r->l->l = cur;
				cur->r = cur->r->l;
				cur->key--;
				cnt++;
			}
		}
		printf("%d ",cur->key);
		cur = cur->r;
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
zalmoxis.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&cur);
   ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70