UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215362#2777. 2048stawalr100115ms21756kbC++112.6kb2024-11-28 21:12:582024-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();
    }
}

详细

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

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