NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #215382 | #2777. 2048 | naroto2022 | 100 | 93ms | 45632kb | C++11 | 2.1kb | 2024-11-28 22:18:18 | 2024-11-28 23:14:05 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cassert>
using namespace std;
const int MN=1005,MM=10005;
long long n,a[MN],pre[MN],lst[MN][MM],hb[MM];
bool dp[MN][MM],frm[MN][MM];
void write(long long n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
long long read(){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
long long lowbit(long long x){return x&-x;}
void print(long long n, long long s){
if(!n) return;
print(n-1,lst[n][s]);
if(frm[n][s]) putchar('r');
else putchar('l');
return;
}
int main(){
for(int i=0; i<=13; i++) hb[1<<i]=(1<<i);
for(int i=0; i<=10000; i++) if(!hb[i]) hb[i]=hb[i-1];
n=read();
for(int i=1; i<=n; i++){a[i]=read();pre[i]=pre[i-1]+a[i];}
long long tot=pre[n];
if(tot!=lowbit(tot)){printf("no");return 0;}
dp[0][0]=1;
for(int i=0; i<n; i++){
if(i) for(int j=0; j<=pre[i]; j++) if(dp[i][j]){
long long l=j,r=pre[i]-j;
assert(hb[l&r]!=hb[l|r]);
if(l<r){
long long ll=l+hb[r],rr=r-hb[r];
dp[i][ll]=1,frm[i][ll]=frm[i][j],lst[i][ll]=lst[i][j];
}
else{
long long ll=l-hb[l],rr=r+hb[l];
dp[i][ll]=1,frm[i][ll]=frm[i][j],lst[i][ll]=lst[i][j];
}
}
for(int j=0; j<=pre[i]; j++) if(dp[i][j]){
long long l=j,r=pre[i]-j,v=a[i+1];
if(!l||v<=lowbit(l)){
long long nl=l+v,h=hb[nl&r];
if(hb[nl|r]==h) nl+=h;
dp[i+1][nl]=1,frm[i+1][nl]=0,lst[i+1][nl]=j;
}
if(!r||v<=lowbit(r)){
long long nr=r+v,h=hb[l&nr];
if(hb[l|nr]==h) l+=h;
dp[i+1][l]=1,frm[i+1][l]=1,lst[i+1][l]=j;
}
}
}
if(dp[n][tot]) print(n,tot);
else if(dp[n][0]) print(n,0);
else printf("no");putchar('\n');
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 1316kb
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: 0ms
memory: 1608kb
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: 0ms
memory: 1560kb
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: 1668kb
input:
20 1 1 2 2 2 8 16 64 32 128 512 128 128 512 512 1024 1024 2048 1024 1024
output:
rrrrrrrlrrlrrrrrrlll
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 1304kb
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: 0ms
memory: 1668kb
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: 0ms
memory: 1456kb
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: 0ms
memory: 1344kb
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: 1688kb
input:
20 1 1 4 8 2 128 128 16 512 32 64 128 512 512 2048 512 256 256 1024 2048
output:
rrllrllrlrrrrrrlllll
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 1372kb
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: 1524kb
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: 1320kb
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: 2268kb
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: 0ms
memory: 1656kb
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: 2576kb
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: 0ms
memory: 2000kb
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: 2364kb
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:
rrrrrrrllrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 1324kb
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: 0ms
memory: 2192kb
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: 2364kb
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:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrlrrrrlllll
result:
ok ok
Subtask #3:
score: 40
Accepted
Test #21:
score: 40
Accepted
time: 11ms
memory: 44080kb
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:
rrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrllllllllllrrrrrrrrrrrrrrrrrrrrrrrllllllllllllllllllllllllllllllllll...
result:
ok ok
Test #22:
score: 0
Accepted
time: 12ms
memory: 42748kb
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:
rrlrrllrrrrllllrrrrrrrrlllllllrrrrrrrlrrrrrrrrllllrrrrrrlllrlllrrrrllllllllllllllllllrrrrrrrrrrrrrrr...
result:
ok ok
Test #23:
score: 0
Accepted
time: 11ms
memory: 38960kb
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:
rrlrrllrrrrlllrrrrrlrrlllllllrrrrrrrrrrrrrrrlllllrrlllllllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrr...
result:
ok ok
Test #24:
score: 0
Accepted
time: 13ms
memory: 40680kb
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:
rrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlllrllrrrrrrlrlrrrrrrrrrrrrrrrrrrrlllrrrrrllllllrrrrr...
result:
ok ok
Test #25:
score: 0
Accepted
time: 11ms
memory: 30388kb
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:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...
result:
ok ok
Test #26:
score: 0
Accepted
time: 4ms
memory: 35864kb
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:
rrlrrllrrrrlllrrrlrrrrllllrrrrrrrlllllllllllrrrrrrrrlrrrrrrrrrrrrrrrrrrrrllllllllllllllrrrrrrrrrrrrr...
result:
ok ok
Test #27:
score: 0
Accepted
time: 8ms
memory: 45632kb
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: 0ms
memory: 30412kb
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:
rrlrrllrrrrllllrrrrrrrrlllllllrrrrrrrrrlrrrrlllllllrrrrrrrrrrrrrlrrrrrrrrrrrlllrllllllllllllllllllll...
result:
ok ok
Test #29:
score: 0
Accepted
time: 8ms
memory: 29836kb
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: 15ms
memory: 38792kb
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:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed
