oj.uz

Submission #127737

# Submission time Handle Problem Language Result Execution time Memory
127737 2019-07-10T04:41:07 Z abacaba Zalmoxis (BOI18_zalmoxis) C++14
5 / 100
 615 ms 262148 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 START_VALUE = 30;
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;
 
map <int, vector <pnode> > is;
vector <pnode> fr;
 
pnode root, last;
stack <pair <int, pnode> > st, temp;

inline void processforward() {
	while(last && k) {
	    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));
	    if(!last->next)
	    	break;
		last = last->next;
	}
}

inline void processback() {
	while(last && k) {
	    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->next = st.top().se;
	        x->prev = st.top().se->prev;
	        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));
	    if(!last->prev)
	    	break;
		last = last->prev;
	}
}

inline void addelse() {
	while(!st.empty()) {
	    int now = st.top().f;
	    temp.push(st.top());
	    st.pop();
	    while(!st.empty() && st.top().f > now + 1) {
	        int need = st.top().f - 1;
	        pnode x = new node(need);
	        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);
	        st.push(mp(need, x));
	        --k;
	    }
	}
}

inline void checkend() {
	st = temp;
	if(!st.empty() && st.top().f != START_VALUE) {
	    last = st.top().se;
	    pnode x = new node(st.top().f);
	    x->prev = last;
	    if(x->prev)
            x->prev->next = x;
        fr.pb(x);
        --k;
	}
}

inline void extend_added() {
	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;
	}
}

inline void output() {
	while(root) {
		printf("%d ", root->val);
		root = root->next;
	}
}

int main() {
    scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	root = new node(a[1]);
	is[a[1]].pb(root);
	last = root;
	for(int i = 2; i <= n; ++i) {
		pnode x = new node(a[i]);
		x->prev = last;
		last->next = x;
		last = x;
		is[a[i]].pb(x);
	}
	last = root;
	processforward();
	addelse();
	processback();
	checkend();
	extend_added();
	output();
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'void processforward()':
zalmoxis.cpp:54:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(x->prev)
             ^~
zalmoxis.cpp:56:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
          fr.pb(x);
          ^~
zalmoxis.cpp:68:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(!last->next)
      ^~
zalmoxis.cpp:70:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   last = last->next;
   ^~~~
zalmoxis.cpp: In function 'void processback()':
zalmoxis.cpp:87:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(x->prev)
             ^~
zalmoxis.cpp:89:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
          fr.pb(x);
          ^~
zalmoxis.cpp:101:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(!last->prev)
      ^~
zalmoxis.cpp:103:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   last = last->prev;
   ^~~~
zalmoxis.cpp: In function 'void extend_added()':
zalmoxis.cpp:154:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(a->prev)
      ^~
zalmoxis.cpp:156: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:170: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:172:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 596 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 597 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 596 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 590 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 599 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 595 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 43568 KB Unexpected end of file - int32 expected
2 Runtime error 615 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 307 ms 45560 KB Output is correct
4 Incorrect 294 ms 45216 KB Unexpected end of file - int32 expected
5 Incorrect 253 ms 44316 KB Unexpected end of file - int32 expected
6 Incorrect 283 ms 45264 KB Unexpected end of file - int32 expected
7 Incorrect 226 ms 43624 KB Unexpected end of file - int32 expected
8 Incorrect 312 ms 44548 KB Unexpected end of file - int32 expected
9 Incorrect 272 ms 46000 KB Unexpected end of file - int32 expected
10 Incorrect 218 ms 55548 KB Unexpected end of file - int32 expected
11 Incorrect 257 ms 51512 KB Unexpected end of file - int32 expected
12 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
13 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
14 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected