UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187398#3366. 如果我的"私人车道"让你差点死掉......Alan_Zhaoyz100686ms36436kbC++111.5kb2023-10-02 09:19:312023-10-02 12:43:47

answer

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=1e6+5;
int n,flg[N];
ll B,b[N],a[N],val[N],dif[N];
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>B;
	deque<ll> dq;
	ll k=1,tag=0,l=0,r=B;
	For(i,2,n-1){
		cin>>b[i];
		r=min(r,b[i]);
		if(l<=r&&r==b[i]){
			flg[i]=1,l=0,dq.clear();
			continue;
		}
		if(~k){
			while(dq.size()&&dq.back()+tag>b[i]) dq.pop_back();
			if(dq.size()&&dq.back()+tag==b[i]){
				flg[i]=1,l=0,r=b[i],dq.clear();
				continue;
			}
		}else{
			while(dq.size()&&-dq.front()+tag>b[i]) dq.pop_front();
			if(dq.size()&&-dq.front()+tag==b[i]){
				flg[i]=1,l=0,r=b[i],dq.clear();
				continue;
			}
		}
		if(l>r&&!dq.size()){
			cout<<"NO\n";return 0;
		}
		val[i]=(dq.size()?k*dq.front()+tag:l);
		tie(l,r)=make_pair(b[i]-r,b[i]-l);
		tag=b[i]-tag,k*=-1;
		if(~k) dq.push_back(b[i]-tag);
		else dq.push_front(-b[i]+tag);
	}
	ll cur=(dq.size()?k*dq.front()+tag:l);
	Dec(i,n-1,2){
		dif[i]=cur;
		if(flg[i]) cur=b[i];
		else if(cur==b[i]) cur=val[i];
		else cur=b[i]-cur;
	}
	cout<<"YES\n";
	a[2]=cur;
	For(i,3,n){
		if(max({a[i-1]+dif[i-1],a[i-1],a[i-2]})-min({a[i-1]+dif[i-1],a[i-1],a[i-2]})==b[i-1]){
			a[i]=a[i-1]+dif[i-1];
		}else{
			a[i]=a[i-1]-dif[i-1];
		}
	}
	ll mn=*min_element(a+1,a+n+1);
	For(i,1,n) cout<<a[i]-mn<<" \n"[i==n];
	return 0;
}

详细

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

Test #1:

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

input:

5 5
5 2 4

output:

YES
0 5 3 3 7

result:

ok ok accepted

Test #2:

score: 10
Accepted
time: 1ms
memory: 1248kb

input:

100 100
31 49 96 28 66 70 53 100 95 86 63 60 15 33 76 84 2 49 56 59 19 26 43 31 68 2 48 31 74 45 77 ...

output:

NO

result:

ok ok accepted

Test #3:

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

input:

100 100
60 47 90 85 85 76 11 11 36 36 95 74 68 92 92 88 88 75 44 71 71 55 10 60 61 10 66 61 61 73 22...

output:

YES
39 99 52 57 142 57 133 122 133 133 169 148 74 142 142 234 146 234 159 203 203 274 219 229 220 16...

result:

ok ok accepted

Test #4:

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

input:

5000 5000
462 3837 4536 4536 4843 4843 3832 2971 4818 4818 4487 3737 2472 3046 1854 4575 4575 1071 2...

output:

YES
237 699 699 4536 0 0 4843 1011 3982 3982 8800 4313 8050 5578 6770 8624 8624 13199 12128 12890 14...

result:

ok ok accepted

Test #5:

score: 10
Accepted
time: 4ms
memory: 1476kb

input:

5000 5000
4436 1076 1527 4838 4838 2504 2504 1976 2785 3755 2137 2957 820 705 1636 1642 2099 2418 24...

output:

YES
2897 7333 6257 6257 7784 2946 5450 2946 4922 3755 2137 0 2137 2957 2252 2252 3888 2246 1789 4207...

result:

ok ok accepted

Test #6:

score: 10
Accepted
time: 2ms
memory: 1476kb

input:

5000 1000000000000
492732137757 902974898827 902974898827 681753346930 921882917490 921882917490 833...

output:

YES
0 492732137757 492732137757 1395707036584 713953689654 713953689654 1635836607144 802234490944 1...

result:

ok ok accepted

Test #7:

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

input:

5000 1000000000000
327710986269 528107212809 271812345489 634989772048 659000595808 886265363665 886...

output:

YES
1405969799952 1733680786221 1477385918901 1205573573412 1205573573412 1840563345460 118156274965...

result:

ok ok accepted

Test #8:

score: 10
Accepted
time: 214ms
memory: 36436kb

input:

1000000 1000000000000
633368376660 585948191319 777876005524 777876005524 283024261193 471473267165 ...

output:

YES
0 633368376660 47420185341 47420185341 825296190865 542271929672 825296190865 1013745196837 1415...

result:

ok ok accepted

Test #9:

score: 10
Accepted
time: 225ms
memory: 36432kb

input:

1000000 1000000000000
961638023220 961638023220 609210401338 782680893626 952270863324 982106329000 ...

output:

YES
0 961638023220 0 609210401338 609210401338 1391891294964 1561481264662 579374935662 135986095456...

result:

ok ok accepted

Test #10:

score: 10
Accepted
time: 240ms
memory: 36436kb

input:

1000000 1000000000000
592659481381 441698394445 318379565687 372681986367 372681986367 646207877102 ...

output:

YES
0 592659481381 150961086936 469340652623 469340652623 842022638990 842022638990 1488230516092 50...

result:

ok ok accepted