ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215362 | #2777. 2048 | stawalr | 100 | 115ms | 21756kb | C++11 | 2.6kb | 2024-11-28 21:12:58 | 2024-11-28 23:12:35 |
answer
#include<bits/stdc++.h>
using namespace std;
const int mn=1005,ma=8193;
bool FLA;
int f[2][ma],lt[ma];
int pre[mn][ma],op[mn][ma];
int t,a[mn],sum,n;
bool FLB;
int lowbit(int x)
{
return x&(-x);
}
void init()
{
lt[1]=0;
for(int i=2;i<ma-1;i++)
{
lt[i]=lt[i>>1]+1;
}
}
void out(int x,int y)
{
if(x==0)return;
out(x-1,pre[x][y]);
printf("%c",op[x][y]?'l':'r');
}
int solve()
{
scanf("%d",&n);
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(lowbit(sum)!=sum)
{
printf("no\n");
return 0;
}
for(int i=0;i<=sum;i++)
{
f[0][i]=f[1][i]=-1;
}
// cerr<<"hi";
f[0][0]=0;
t=0;
for(int i=1;i<=n;i++)
{
t^=1;
for(int j=0;j<=sum;j++)
{
// cerr<<f[t^1][j]<<" ";
f[t][j]=-1;
// pre[i][j]=0;
// op[i][j]=0;
}
// cerr<<'\n';
for(int j=0;j<=sum;j++)
{
if(f[t^1][j]==-1)continue;
if(j==0)//1
{
f[t][a[i]]=0;
pre[i][a[i]]=0;
op[i][a[i]]=0;
continue;
}
if(f[t^1][j]==0)
{
if(lt[a[i]]>=lt[j])//2
{
f[t][j+a[i]]=0;
pre[i][j+a[i]]=j;
op[i][j+a[i]]=1;
}
else
{
f[t][j]=a[i];
pre[i][j]=j;
op[i][j]=1;
}
}
if(lowbit(j)>=a[i])//3
{
f[t][j+a[i]]=f[t^1][j];
pre[i][j+a[i]]=j;
op[i][j+a[i]]=0;
}
if(lowbit(f[t^1][j])>=a[i])//4
{
if(lt[f[t^1][j]+a[i]]==lt[j])
{
f[t][j+(1<<lt[j])]=f[t^1][j]+a[i]-(1<<lt[j]);
pre[i][j+(1<<lt[j])]=j;
op[i][j+(1<<lt[j])]=1;
}
else
{
f[t][j]=f[t^1][j]+a[i];
pre[i][j]=j;
op[i][j]=1;
}
}
}
}
// cerr<<"hi";
if(f[t][sum]!=0)
{
printf("no");
}
else
{
out(n,sum);
}
printf("\n");
return 0;
}
int main()
{
// cerr<<(&FLA-&FLB)/1024.0/1024.0;
init();
int T=1;
// scanf("%d",&T);
while(T--)
{
solve();
}
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 1ms
memory: 1336kb
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: 1432kb
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: 1ms
memory: 1416kb
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: 1540kb
input:
20 1 1 2 2 2 8 16 64 32 128 512 128 128 512 512 1024 1024 2048 1024 1024
output:
rrrrrrrlrrlrrrrrrrrr
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 1328kb
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: 1504kb
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: 1404kb
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: 3ms
memory: 1352kb
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: 1500kb
input:
20 1 1 4 8 2 128 128 16 512 32 64 128 512 512 2048 512 256 256 1024 2048
output:
rrllrllrlrrrrrrrrrrr
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 1364kb
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: 1ms
memory: 1472kb
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: 1ms
memory: 1344kb
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: 1704kb
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: 1528kb
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: 1ms
memory: 1904kb
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: 1608kb
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: 1764kb
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: 1344kb
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: 1736kb
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: 1868kb
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:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrllrrrrrrrrrr
result:
ok ok
Subtask #3:
score: 40
Accepted
Test #21:
score: 40
Accepted
time: 13ms
memory: 20600kb
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:
rrrrrrrrrrrrrrrrrrrrrrlrlllllllllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...
result:
ok ok
Test #22:
score: 0
Accepted
time: 11ms
memory: 19540kb
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: 12ms
memory: 18984kb
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:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlllllllllllllllllllllllllllllllllllllllllllllllllllllllrrlllllr...
result:
ok ok
Test #24:
score: 0
Accepted
time: 12ms
memory: 19428kb
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:
rrrrrlllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllrrrrrrrrrrllllllllllllllllllllllll...
result:
ok ok
Test #25:
score: 0
Accepted
time: 8ms
memory: 15896kb
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: 12ms
memory: 17728kb
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:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...
result:
ok ok
Test #27:
score: 0
Accepted
time: 11ms
memory: 21756kb
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: 12ms
memory: 16124kb
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:
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlllllllllllllrlllllllllllrrrlrrrrrrrrrrrrrrrrrrrr...
result:
ok ok
Test #29:
score: 0
Accepted
time: 8ms
memory: 16688kb
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: 7ms
memory: 18976kb
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