UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215384#2777. 2048erican06ms3360kbC++113.1kb2024-11-28 22:30:462024-11-28 23:14:09

answer

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
// void write(int out) {
// 	if (out < 0)
// 		putchar('-'), out = -out;
// 	if (out > 9)
// 		write(out / 10);
// 	putchar(out % 10 + '0');
// }
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (int v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 1e4 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

int ans[1005],top;
int lst[1005][N];

int a[1005],pre[1005];
bool f[1005][N];


inline int lowbit(int x){
    return x&-x;
}
inline bool check(int a){
    int x=a;
    int res=0;
    while(a){
        res+=a&1;
        a>>=1;
    }

    if(res==1)return 1;
    if(res>2)return 0;
    return lowbit(x)==lowbit(x>>14);
}

inline bool able(int a,int x){
    if(lowbit(a)<x&&a)return 0;
    return 1;
}

int n;

bool fcheck(){
    list<int> ls;
    int i=0;
    for(int j=n;j;j--){
		i++;
        int v=ans[j];
		if(!v){
			while(ls.size()&&ls.front()==a[i])ls.pop_front(),a[i]<<=1;
			ls.push_front(a[i]);
		}else {
			while(ls.size()&&ls.back()==a[i])ls.pop_back(),a[i]<<=1;
			ls.push_back(a[i]);
		}
	}
    return ls.size()==1;
}

void solve() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);


     n=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
        pre[i]=pre[i-1]+a[i];
    }


    // f.reset();

    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int s=0;s<=pre[i-1];s++){
            if(f[i-1][s]){
                if(able(s,a[i])){
                    // cdbg("L",s,i);
                    f[i][s+a[i]]=1;
                    lst[i][s+a[i]]=s;
                } 
                if(able(pre[i-1]-s,a[i])){
                    // cdbg("R",s,i);
                    f[i][s]=1;
                    lst[i][s]=s;
                }
            }

        }
    }


    for(int s=0;s<=pre[n];s++){
        // if(f[s])cdbg(s);
        if(f[n][s]&&check(s<<14|(pre[n]-s))==1){
            // cdbg(s);
            int cur=n;
            while(cur){
                ans[++top]=(lst[cur][s]==s);
                s=lst[cur--][s];
            }

            if(!fcheck())break; //!!!

            while(n){
                if(ans[n--])putchar('r');
                else putchar('l');
            }
            puts("");
            return ;
        }
    }

    puts("no");
}

signed main(){
    solve();
}

详细

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 1356kb

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: 1164kb

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: -30
Wrong Answer
time: 0ms
memory: 1216kb

input:

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

output:

no

result:

wrong answer participant output is not correct

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 30
Accepted
time: 1ms
memory: 1352kb

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: 1232kb

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: 1564kb

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: 1424kb

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: 1960kb

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: 1268kb

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: -30
Wrong Answer
time: 0ms
memory: 1296kb

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:

no

result:

wrong answer participant output is not correct

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 5ms
memory: 3360kb

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:

no

result:

wrong answer participant output is not correct