oj.uz

답안 #127733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127733 2019-07-10T04:20:26 Z abacaba Zalmoxis (BOI18_zalmoxis) C++14
5 / 100
 1000 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 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 = NULL, last;
stack <pair <int, pnode> > st;
 
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;
	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 = last;
	        x->prev = last->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->next)
	    	break;
		last = last->next;
	}
	stack <pair <int, pnode> > temp;
	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 = temp.top().se;
	        if(x->next)
    	        x->next->prev = x;
            if(x->prev)
	            x->prev->next = x;
	        fr.pb(x);
	        st.push(mp(need, x));
	        --k;
	    }
	}

	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 = last;
	        x->prev = last->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;
	}

	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 = temp.top().se;
	        if(x->next)
    	        x->next->prev = x;
            if(x->prev)
	            x->prev->next = x;
	        fr.pb(x);
	        st.push(mp(need, x));
	        --k;
	    }
	}

	st = temp;

	if(!st.empty() && st.top().f != 30) {
	    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;
	}
	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;
	}
	while(root) {
		printf("%d ", root->val);
		root = root->next;
	}
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:67:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(x->prev)
             ^~
zalmoxis.cpp:69:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
          fr.pb(x);
          ^~
zalmoxis.cpp:81:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(!last->next)
      ^~
zalmoxis.cpp:83:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   last = last->next;
   ^~~~
zalmoxis.cpp:117:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(x->prev)
             ^~
zalmoxis.cpp:119:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
          fr.pb(x);
          ^~
zalmoxis.cpp:131:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(!last->prev)
      ^~
zalmoxis.cpp:133:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   last = last->prev;
   ^~~~
zalmoxis.cpp:178:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(a->prev)
      ^~
zalmoxis.cpp:180:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   fr.pb(a);
   ^~
zalmoxis.cpp:41: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:43: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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 592 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 348 ms 72480 KB Expected EOF
3 Incorrect 316 ms 56104 KB Expected EOF
4 Incorrect 289 ms 48232 KB Expected EOF
5 Runtime error 586 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Incorrect 407 ms 83680 KB Expected EOF

Subtask #2
5.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 599 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 623 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 305 ms 45672 KB Output is correct
4 Runtime error 597 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 593 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 592 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 595 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 351 ms 67848 KB Expected EOF
9 Execution timed out 1084 ms 74380 KB Time limit exceeded
10 Execution timed out 1075 ms 86840 KB Time limit exceeded
11 Execution timed out 1079 ms 81092 KB Time limit exceeded
12 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
13 Execution timed out 1084 ms 28408 KB Time limit exceeded
14 Incorrect 2 ms 256 KB Unexpected end of file - int32 expected