oj.uz

Submission #127858

# Submission time Handle Problem Language Result Execution time Memory
127858 2019-07-10T07:21:32 Z abacaba Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 254 ms 65168 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
const int inf = 2e9;
const int N = 1e6 + 15;
int n, k, a[N];
 
struct node {
	node *prev, *next;
	int val;
	node(int val) : val(val) {
		prev = next = NULL;
	}
};
 
typedef node* pnode;

vector <pnode> fr;
 
pnode root, last;
stack <pair <int, pnode> > st, temp;
 
void processnext() {
	while(last) {
	    int now = last->val;
	    while(!st.empty() && st.top().f == now) {
	        st.pop();
	        ++now;
	    }
	    while(!st.empty() && st.top().f < now) {
	        pnode x = new node(st.top().f);
	        x->prev = st.top().se;
	        x->next = st.top().se->next;
	        if(x->next)
	            x->next->prev = x;
            if(x->prev)
                x->prev->next = x;
	        fr.pb(x);
	        int curval = x->val;
	        while(!st.empty() && st.top().f == curval)
	            st.pop(), ++curval;
	        st.push(mp(curval, x));
	        --k;
	    }
	    while(!st.empty() && st.top().f == now) {
	        st.pop();
	        ++now;
	    }
	    st.push(mp(now, last));
		last = last->next;
	}
}

void checkend() {
	while(!st.empty() && st.top().f != 30) {
		last = st.top().se;
	   	pnode x = new node(st.top().f);
		x->prev = last;
		int now = x->val;
	    if(x->prev)
   	    	x->prev->next = x;
	    fr.pb(x);
        --k;
		while(!st.empty() && st.top().f == now) {
		    st.pop();
		   	++now;
	    }
	    st.push(mp(now, x));
	}
}

void extend_fr() {
	while(!fr.empty() && k) {
		pnode x = fr.back();
		fr.ppb();
		if(x->val <= 1)
			continue;
		pnode a = new node(x->val - 1), b = new node(x->val - 1);
		a->prev = x->prev;
		a->next = b;
		b->prev = a;
		b->next = x->next;
		if(b->next)
    		b->next->prev = b;
    	if(a->prev)
    		a->prev->next = a;
		fr.pb(a);
		fr.pb(b);
		--k;
	}
}

int main() {
    scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	root = new node(a[1]);
	last = root;
	for(int i = 2; i <= n; ++i) {
		pnode x = new node(a[i]);
		x->prev = last;
		last->next = x;
		last = x;
	}
	last = root;
	processnext();
	checkend();
	extend_fr();
	while(root) {
		printf("%d ", root->val);
		root = root->next;
	}
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'void processnext()':
zalmoxis.cpp:52:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(x->prev)
             ^~
zalmoxis.cpp:54:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
          fr.pb(x);
          ^~
zalmoxis.cpp: In function 'void extend_fr()':
zalmoxis.cpp:101:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(a->prev)
      ^~
zalmoxis.cpp:103:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   fr.pb(a);
   ^~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 37624 KB Output is correct
2 Correct 247 ms 37664 KB Output is correct
3 Correct 245 ms 37688 KB Output is correct
4 Correct 245 ms 37624 KB Output is correct
5 Correct 245 ms 37624 KB Output is correct
6 Correct 245 ms 37668 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 37624 KB Output is correct
2 Correct 254 ms 37624 KB Output is correct
3 Correct 248 ms 37840 KB Output is correct
4 Correct 246 ms 37624 KB Output is correct
5 Correct 246 ms 37840 KB Output is correct
6 Correct 246 ms 37600 KB Output is correct
7 Correct 249 ms 37752 KB Output is correct
8 Correct 248 ms 37744 KB Output is correct
9 Correct 240 ms 40016 KB Output is correct
10 Correct 223 ms 53732 KB Output is correct
11 Correct 232 ms 47716 KB Output is correct
12 Correct 213 ms 65016 KB Output is correct
13 Correct 210 ms 64984 KB Output is correct
14 Correct 212 ms 65168 KB Output is correct