oj.uz

답안 #932272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932272 2024-02-23T06:53:55 Z pcc Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 126 ms 71096 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


int N,K;

struct node{
	int pl,pr,val,match;
	node(){
		pl = pr = val = match = 0;
	}
};
const int mxn = 1e6+10;
node arr[mxn*4];
int brr[mxn];
int pp = 1;
int rt = 1;
int sz = 1;

int newnode(){
	return ++pp;
}


void split(int now){
	sz++;
	arr[now].val--;
	int nxt = newnode();
	arr[nxt].val = arr[now].val;
	arr[arr[now].pr].pl = nxt;
	arr[nxt].pr = arr[now].pr;
	arr[nxt].pl = now;
	arr[now].pr = nxt;
	return;
}

void pv(int now){
	while(now){
		cout<<arr[now].val<<' ';now = arr[now].pr;
	}
	cout<<endl;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<=N;i++)cin>>brr[i];
	int now = rt;
	arr[rt].val = 30;
	for(int i = 1;i<=N;i++){
		while(arr[now].val<brr[i]){
			now = arr[now].pr;
		}
		while(arr[now].val>brr[i]){
			split(now);
		}
		//cout<<i<<' '<<now<<":"<<arr[now].val<<','<<arr[now].pr<<','<<brr[i]<<endl;
		//pv(rt);
		arr[now].match = true;
		now = arr[now].pr;
	}
	now = rt;
	while(now){
		while(sz<N+K&&!arr[now].match&&arr[now].val>0){
			split(now);
		}
		now = arr[now].pr;
	}
	now = rt;
	while(now){
		cout<<arr[now].val<<' ';
		now = arr[now].pr;
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 70892 KB Output is correct
2 Correct 120 ms 71060 KB Output is correct
3 Correct 126 ms 71096 KB Output is correct
4 Correct 113 ms 70996 KB Output is correct
5 Correct 115 ms 70996 KB Output is correct
6 Correct 113 ms 70904 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 71072 KB Output is correct
2 Correct 113 ms 70992 KB Output is correct
3 Correct 118 ms 71060 KB Output is correct
4 Correct 115 ms 70996 KB Output is correct
5 Correct 118 ms 71068 KB Output is correct
6 Correct 112 ms 70992 KB Output is correct
7 Correct 116 ms 70916 KB Output is correct
8 Correct 115 ms 70940 KB Output is correct
9 Correct 107 ms 70668 KB Output is correct
10 Correct 97 ms 69648 KB Output is correct
11 Correct 93 ms 69968 KB Output is correct
12 Correct 82 ms 66644 KB Output is correct
13 Correct 65 ms 66848 KB Output is correct
14 Correct 66 ms 66644 KB Output is correct