UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214412#2386. 回忆meixuan20500ms1632kbC++11931b2024-11-18 20:32:412024-11-19 08:32:35

answer

#include<bits/stdc++.h>
using namespace std;
int t[100001];
int a[301];
priority_queue<int> q;
int n,m;
int check(int mid){
	a[1]=mid;
	a[2]=t[1]-mid;
	a[3]=t[2]-mid;
	q.push(a[2]+a[3]);
	int now=3;
	for(int i=3;i<=m;i++){
		if(now==n)break;
		if(q.empty()||t[i]!=q.top()){
			now++;
			a[now]=t[i]-a[1];
			for(int i=2;i<=now;i++){
				q.push(a[i]+a[now]);
			}
		}else q.pop();
	}
//	for(int i=1;i<=n;i++)cout <<a[i]<<' ';
//	cout <<endl;
}
void init(){
	while(!q.empty())q.pop();
	for(int i=1;i<=n;i++)a[i]=0;
}
int main(){
	cin >>n;
	m=((n-1)*n)/2;
	for(int i=1;i<=m;i++)cin >>t[i];
	sort(t+1,t+m+1);
	int l=1,r=t[1]-1,ans=0;
	while(l<=r){
		int mid=l+r>>1;
		check(mid);
	//	cout <<mid<<' '<<a[n]<<' '<<a[n-1]<<endl;
		if(a[n]+a[n-1]<=t[m]){
			ans=mid;
			r=mid-1;
		}else l=mid+1;
		//cout <<l<<' '<<r<<endl;
		init();
	}
	check(ans);
	for(int i=1;i<=n;i++)cout <<a[i]<<' ';
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1256kb

input:

5
4 5 9 9 10 13 14 14 15 19

output:

1 3 4 8 8 

result:

wrong answer Your answer is incorrect.

Test #2:

score: 10
Accepted
time: 0ms
memory: 1252kb

input:

5
5 9 9 10 12 12 13 16 17 17

output:

1 4 8 8 9 

result:

ok Your answer is correct.

Test #3:

score: 10
Accepted
time: 0ms
memory: 1256kb

input:

5
10 11 12 13 13 14 15 15 16 17

output:

4 6 7 8 9 

result:

ok Your answer is correct.

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 1280kb

input:

50
9 13 15 20 20 20 21 22 22 26 26 26 27 27 27 28 29 31 31 32 32 33 33 33 33 33 34 34 34 35 35 36 37...

output:

1 8 12 14 19 19 19 20 21 21 25 25 25 26 26 26 27 28 30 30 31 31 32 32 32 32 32 33 33 33 34 34 35 36 ...

result:

wrong answer Your answer is incorrect.

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 1276kb

input:

50
9 11 14 14 16 16 16 18 19 19 21 21 21 21 22 22 23 23 23 23 24 25 25 26 26 26 26 26 26 26 27 27 27...

output:

1 8 10 13 13 15 15 15 17 18 18 20 20 20 20 21 21 22 22 22 22 23 24 24 25 25 25 25 25 25 25 26 26 26 ...

result:

wrong answer Your answer is incorrect.

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 1276kb

input:

50
7 9 12 16 19 21 26 27 29 29 31 33 33 33 34 35 36 36 36 36 37 38 38 38 38 39 39 40 40 40 41 41 42 ...

output:

1 6 8 11 15 18 20 25 26 28 28 30 32 32 32 33 34 35 35 35 35 36 37 37 37 37 38 38 39 39 39 40 40 41 4...

result:

wrong answer Your answer is incorrect.

Test #7:

score: 0
Wrong Answer
time: 112ms
memory: 1632kb

input:

300
660422 717145 1052261 1191442 1526558 1583281 1636913 1972029 2028752 2207583 2247577 2427928 25...

output:

1 660421 717144 1052260 1191441 1526557 1583280 1636912 1972028 2028751 2207582 2247576 2427927 2503...

result:

wrong answer Your answer is incorrect.

Test #8:

score: 0
Wrong Answer
time: 134ms
memory: 1628kb

input:

300
1719032 1728175 1968715 2265775 2506315 2515458 2534303 2752316 3002166 3035709 3071903 3081046 ...

output:

1 1719031 1728174 1968714 2265774 2506314 2515457 2534302 2752315 3002165 3035708 3071902 3081045 32...

result:

wrong answer Your answer is incorrect.

Test #9:

score: 0
Wrong Answer
time: 122ms
memory: 1628kb

input:

300
725653 809390 819383 974701 984694 1058923 1068431 1068916 1152653 1317964 1422171 1432164 15159...

output:

1 725652 809389 819382 974700 984693 1058922 1068430 1068915 1152652 1317963 1422170 1432163 1515900...

result:

wrong answer Your answer is incorrect.

Test #10:

score: 0
Wrong Answer
time: 130ms
memory: 1628kb

input:

300
2355315 3132486 3240117 3325566 3662015 3854305 3961936 4047385 4053636 4142315 4383834 4725290 ...

output:

1 2355314 3132485 3240116 3325565 3662014 3854304 3961935 4047384 4053635 4142314 4383833 4725289 47...

result:

wrong answer Your answer is incorrect.