UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215360#2777. 2048fddwd1004235ms63560kbC++111.7kb2024-11-28 21:07:142024-11-28 23:12:18

answer

#include<bits/stdc++.h>
using namespace std;
#define pint pair<int,int>
#define fir first
#define sec second
#define lowbit(i) (i&-i)
int n,a[1010];
map<pint,pair<pint,bool>>dp[1010];
inline void merge(int &x,int &y){
	for(int i=13;~i;--i){
		if((x>>i)&1){
			if((y>>i)&1) x+=(1<<i),y-=(1<<i);
			return;
		}if((y>>i)&1) return;
	}
}inline void print(int id,pint spt){
	if(!id) return;
	print(id-1,dp[id][spt].fir);
	cout<<(dp[id][spt].sec?'r':'l');
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;for(int i=1;i<=n;++i) cin>>a[i];
	int all=0;for(int i=1;i<=n;++i) all+=a[i];
	if(__builtin_popcount(all)!=1){cout<<"no"<<endl;return 0;}
	if(n<=20){
		bool flag=false;
		for(int base=0;base<(1<<n);++base){
			deque<int>spt;
			for(int i=0;i<n;++i){
				if((base>>i)&1) spt.push_front(a[i+1]);
				else spt.push_back(a[i+1]);
				while(spt.size()>=2&&spt[0]==spt[1])
					spt.pop_front(),spt.front()<<=1;
				while(spt.size()>=2&&spt.back()==spt[spt.size()-2])
					spt.pop_back(),spt.back()<<=1;
			}if(spt.size()==1){
				flag=true;
				for(int i=0;i<n;++i) cout<<((base>>i)&1?'r':'l');
				cout<<endl;
				break;
			}
		}if(!flag) cout<<"no"<<endl;
		return 0;
	}dp[0][{0,0}]={{0,0},0};
	for(int i=1;i<=n;++i)
	for(auto it=dp[i-1].begin();it!=dp[i-1].end();++it){
		pint spt=it->fir;
		if(!spt.fir||lowbit(spt.fir)>=a[i]){
			pint jev={spt.fir+a[i],spt.sec};
			merge(jev.fir,jev.sec);
			dp[i][jev]={spt,0};
		}if(!spt.sec||lowbit(spt.sec)>=a[i]){
			pint jev={spt.fir,spt.sec+a[i]};
			merge(jev.fir,jev.sec);
			dp[i][jev]={spt,1};
		}
	}if(dp[n].count({all,0}))
		print(n,{all,0}),cout<<endl;
	else if(dp[n].count({0,all}))
		print(n,{0,all}),cout<<endl;
	else cout<<"no"<<endl;
	return 0;
}

详细

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

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 352ms
memory: 1296kb

input:

20
2 8 8 256 2 32 64 64 2 2 64 8 256 128 128 1024 2048 2048 1024 1024

output:

no

result:

ok ok

Test #2:

score: 0
Accepted
time: 414ms
memory: 1296kb

input:

20
1 1 2 4 8 8 8 1024 32 32 16 16 128 1024 1024 128 64 64 4096 512

output:

no

result:

ok ok

Test #3:

score: 0
Accepted
time: 382ms
memory: 1300kb

input:

20
1 2 1 8 4 64 64 4 4 8 2048 32 4096 128 128 64 512 512 256 256

output:

no

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 1300kb

input:

20
1 1 2 2 2 8 16 64 32 128 512 128 128 512 512 1024 1024 2048 1024 1024

output:

lllllllrllrlllllllll

result:

ok ok

Test #5:

score: 0
Accepted
time: 348ms
memory: 1296kb

input:

20
2 4 4 4 2 32 128 8 32 32 128 256 256 256 512 8 128 256 2048 4096

output:

no

result:

ok ok

Test #6:

score: 0
Accepted
time: 550ms
memory: 1296kb

input:

20
1 1 2 1 1 1 1 16 32 128 512 8 64 256 1024 1024 2048 2048 512 512

output:

no

result:

ok ok

Test #7:

score: 0
Accepted
time: 392ms
memory: 1300kb

input:

20
4 4 2 2 8 4 4 4 32 256 128 128 256 32 32 512 512 2048 128 4096

output:

no

result:

ok ok

Test #8:

score: 0
Accepted
time: 353ms
memory: 1300kb

input:

20
8 16 16 16 16 16 2 16 512 4 16 2 64 64 2048 128 128 4096 512 512

output:

no

result:

ok ok

Test #9:

score: 0
Accepted
time: 0ms
memory: 1296kb

input:

20
1 1 4 8 2 128 128 16 512 32 64 128 512 512 2048 512 256 256 1024 2048

output:

llrrlrrlrlllllllllll

result:

ok ok

Test #10:

score: 0
Accepted
time: 354ms
memory: 1300kb

input:

20
2 1 1 2 32 64 128 128 128 2 512 512 256 256 2048 2048 8 1024 1024 16

output:

no

result:

ok ok

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 0ms
memory: 1304kb

input:

50
1 1 2 2 8 8 8 8 1 1 16 8 8 4 4 8 8 8 64 32 8 8 16 256 256 64 64 128 4 4 256 128 128 256 256 1024 ...

output:

no

result:

ok ok

Test #12:

score: 0
Accepted
time: 0ms
memory: 1304kb

input:

50
1 1 2 2 2 2 4 8 2 2 4 16 4 1 1 2 8 64 64 1 1 128 128 8 1 1 2 4 16 16 8 2 2 4 128 64 64 128 128 20...

output:

no

result:

ok ok

Test #13:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

50
1 1 1 1 4 2 1 1 2 2 4 4 8 32 32 32 32 32 32 64 128 128 64 64 64 16 16 32 16 8 8 64 32 32 128 16 1...

output:

no

result:

ok ok

Test #14:

score: 0
Accepted
time: 1ms
memory: 1312kb

input:

50
1 1 2 2 1 1 2 1 1 1 1 1 1 8 4 4 4 2 2 4 4 16 256 256 256 256 512 512 256 256 2048 512 32 8 8 16 5...

output:

no

result:

ok ok

Test #15:

score: 0
Accepted
time: 0ms
memory: 1324kb

input:

50
8 4 16 4 16 8 1 1 2 4 16 16 32 32 16 16 64 64 64 16 16 16 16 64 128 128 32 32 64 64 64 256 128 64...

output:

no

result:

ok ok

Test #16:

score: 0
Accepted
time: 1ms
memory: 1308kb

input:

50
1 1 1 1 2 2 1 1 1 1 1 1 2 32 32 1024 8 8 32 8 4 1 1 2 32 16 16 64 32 32 16 8 8 32 32 128 128 64 6...

output:

no

result:

ok ok

Test #17:

score: 0
Accepted
time: 0ms
memory: 1328kb

input:

50
1 1 1 1 1 1 2 16 16 8 8 4 4 8 1 1 2 4 256 16 8 8 16 32 32 32 32 512 512 256 32 32 16 16 32 32 32 ...

output:

rrrrrrrllrrrrlllllrllllllllrlllllllllllllllllllllr

result:

ok ok

Test #18:

score: 0
Accepted
time: 0ms
memory: 1300kb

input:

50
1 32 2 1 1 1 1 8 8 4 4 32 32 32 256 32 32 16 16 16 16 512 512 64 64 128 256 512 512 1024 32 1 16 ...

output:

no

result:

ok ok

Test #19:

score: 0
Accepted
time: 1ms
memory: 1320kb

input:

50
1 1 1 1 8 1 1 2 4 2 1 1 128 64 64 128 4 4 1 1 2 2 2 8 2 2 4 8 32 16 8 8 128 128 32 32 32 32 128 5...

output:

no

result:

ok ok

Test #20:

score: 0
Accepted
time: 0ms
memory: 1344kb

input:

50
1 1 1 1 1 1 2 4 2 2 2 2 4 4 1 1 2 16 16 8 2 2 2 2 2 2 1 1 2 4 4 128 8 8 16 64 64 128 1024 1024 51...

output:

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrlllrrllllllllll

result:

ok ok

Subtask #3:

score: 40
Accepted

Test #21:

score: 40
Accepted
time: 154ms
memory: 58980kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 2 1 1 1 1 8 8 16 1 1 1 1 1 1 1 1 16 8 1 1 1 1 1 1 2 8 8 4 4 4 4...

output:

lrllllllllllllllllllllrlrrrrrrrrrlllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok

Test #22:

score: 0
Accepted
time: 160ms
memory: 61124kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4...

output:

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

result:

ok ok

Test #23:

score: 0
Accepted
time: 130ms
memory: 53452kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1...

output:

lrlllllllllllllllllllllllllllllllllllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrl...

result:

ok ok

Test #24:

score: 0
Accepted
time: 128ms
memory: 50952kb

input:

1000
1 1 1 1 1 8 4 4 16 8 8 2 2 4 8 4 2 1 1 2 2 4 8 1 1 2 4 2 2 2 1 1 8 1 1 2 4 4 2 2 32 32 4 2 2 8 ...

output:

rrrrrlllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllrrrrrrrrrrlllllllrrrrrrllllrrrrrrr...

result:

ok ok

Test #25:

score: 0
Accepted
time: 70ms
memory: 33816kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 4 4 1 1 2 1 1 1 1 1 1 2...

output:

lrllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok

Test #26:

score: 0
Accepted
time: 87ms
memory: 38560kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 2 1 1 2 2 4 4 4 1 1 1 1 2 2 2 2 1 1 1 1 1 1...

output:

lrllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok

Test #27:

score: 0
Accepted
time: 152ms
memory: 63560kb

input:

1000
4 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

no

result:

ok ok

Test #28:

score: 0
Accepted
time: 55ms
memory: 26016kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 1 1 1 1 2 2 4...

output:

lrlllllllllllllllllllllllllllllllllllllllllllllllllrrrrrrrrrrrrrlrrrrrrrrrrrlllrllllllllllllllllllll...

result:

ok ok

Test #29:

score: 0
Accepted
time: 64ms
memory: 31828kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

no

result:

ok ok

Test #30:

score: 0
Accepted
time: 87ms
memory: 37364kb

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 2 2 4 1 1 1 1 1 1 1...

output:

lrllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed