oj.uz

Submission #81804

# Submission time Handle Problem Language Result Execution time Memory
81804 2018-10-26T21:44:02 Z Plurm Zalmoxis (BOI18_zalmoxis) C++11
0 / 100
 1000 ms 141712 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 141176 KB Time limit exceeded
2 Execution timed out 1095 ms 141336 KB Time limit exceeded
3 Execution timed out 1088 ms 141616 KB Time limit exceeded
4 Execution timed out 1092 ms 141616 KB Time limit exceeded
5 Execution timed out 1095 ms 141616 KB Time limit exceeded
6 Execution timed out 1095 ms 141616 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 141616 KB Time limit exceeded
2 Execution timed out 1072 ms 141616 KB Time limit exceeded
3 Execution timed out 1091 ms 141616 KB Time limit exceeded
4 Execution timed out 1095 ms 141616 KB Time limit exceeded
5 Execution timed out 1087 ms 141616 KB Time limit exceeded
6 Execution timed out 1090 ms 141616 KB Time limit exceeded
7 Execution timed out 1095 ms 141712 KB Time limit exceeded
8 Execution timed out 1094 ms 141712 KB Time limit exceeded
9 Execution timed out 1089 ms 141712 KB Time limit exceeded
10 Incorrect 939 ms 141712 KB Unexpected end of file - int32 expected
11 Execution timed out 1087 ms 141712 KB Time limit exceeded
12 Incorrect 3 ms 141712 KB Unexpected end of file - int32 expected
13 Incorrect 2 ms 141712 KB Unexpected end of file - int32 expected
14 Incorrect 2 ms 141712 KB Unexpected end of file - int32 expected