UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215349#2777. 2048N70425ms151636kbC++114.8kb2024-11-28 20:24:072024-11-28 23:11:47

answer

//
//  na 2777.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/28.
//

#include <stdio.h>
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
const int maxn = 1005, maxl = 25, lim = 24, spl = 12;
int n, a[maxn], from[1 << maxl], path[maxn];
bool vis[1 << maxl], tp[1 << maxl], ans[maxn];
int qs, qe, qst[1 << maxl | 1], qid[1 << maxl | 1]; // 2^25 for 13
inline void push(int pos, int from_state, int state, bool dir){
    if(!vis[state]){
//        cerr << "push: #" << pos << ", from_state: " << bitset<maxl>(from_state) << ", to_state: " << bitset<maxl>(state) << ", dir = " << boolalpha << dir << noboolalpha << endl;
        vis[state] = true;
        from[state] = from_state;
        tp[state] = dir;
        qst[qe] = state;
        qid[qe++] = pos;
    }
}
inline void pop(int &pos, int &state){
    state = qst[qs];
    pos = qid[qs++];
}
inline int lg2(int x){
    int res = 0;
    while(x >>= 1)
        ++res;
    return res;
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
#ifdef MAC_OS_VERSION_11_0
    freopen("/Users/m2/Downloads/problem_2777/ex_204815.in", "r", stdin);
#endif
    cin >> n;
    int sm = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        sm += a[i];
        a[i] = lg2(a[i]);
    }
    if(sm != (sm & -sm)){
        cout << "no" << endl;
        return 0;
    }
//    cerr << "real seq: ";
//    for(int i = 1; i <= n; ++i)
//        cerr << a[i] << ' ';
//    cerr << endl;
    push(0, 0, 0, false);
    int p = -1, s = -1, v, ns;
    bool found = false;
    while(qs != qe){
        pop(p, s);
        if(p == n){
            if(__builtin_popcount(s) == 1){
                found = true;
                break;
            }
            continue;
        }
        v = a[++p];
        if(!(s & ((1 << v) - 1))){ // ins l
            ns = s;
            while(ns & (1 << v))
                ns ^= 1 << (v++);
            if(v > spl){ // (p = n - 1)
                push(p, s, 1 << maxl, false); // next state
                qs = qe - 1;
                continue;
            }
            if(!((ns & ((1 << (lim - v)) - 1)) >> v) && ns & (1 << (lim - v)))
                push(p, s, 2 << v, false);
            else
                push(p, s, ns ^ (1 << v), false);
            v = a[p];
        }
        if(!(s >> (maxl - v))){ // ins r
            ns = s;
            v = lim - v;
            while(ns & (1 << v))
                ns ^= 1 << (v--);
            if(v < spl){ // (p = n - 1)
                push(p, s, 1 << maxl, true); // next state
                qs = qe - 1;
                continue;
            }
            if(!((ns & ((1 << v) - 1)) >> (maxl - v)) && ns & (1 << (lim - v)))
                push(p, s, 1 << (v - 1), true);
            else
                push(p, s, ns ^ (1 << v), true);
        }
    }
    if(!found){
        cout << "no" << endl;
    }else{
        for(int i = n; i; --i){
            ans[i] = tp[s];
            path[i] = s;
//            cerr << bitset<maxl>(s) << endl;
            s = from[s];
        }
        for(int i = 1; i <= n; ++i)
            if(ans[i])
                cout << "r";
            else
                cout << "l";
        cout << endl;
    }
#ifdef MAC_OS_VERSION_11_0
    {
        vector<int> dq;
        for(int i = 1; i <= n; ++i){
            if(ans[i]){
                dq.insert(dq.begin(), a[i]);
                while(dq.size() >= 2 && dq[0] == dq[1]){
                    dq.erase(dq.begin());
                    ++dq[0];
                }
            }else{
                dq.push_back(a[i]);
                while(dq.size() >= 2 && dq[dq.size() - 1] == dq[dq.size() - 2]){
                    dq.erase(dq.end() - 1);
                    ++dq[dq.size() - 1];
                }
            }
//            cerr << bitset<maxl>(path[i]) << endl;
//            for(int j: dq)
//                cerr << j << ' ';
//            cerr << endl;
//            int p = 0;
//            for(int j = maxl - 1; j >= 0; --j)
//                if(path[i] & (1 << j)){
//                    if(p == dq.size() || dq[p] != min(j, lim - j)){
//                        if(p != dq.size())
//                            cerr << "error state: " << dq[p] << " vs " << j << endl;
//                        cerr << "value: " << a[i] << endl;
//                        cerr << "action: " << boolalpha << tp[path[i]] << noboolalpha << endl;
//                        cerr << "from: " << bitset<maxl>(path[i - 1]) << ", cur: " << bitset<maxl>(path[i]) << endl;
//                        return 0;
//                    }
//                    ++p;
//                }
        }
        if(dq.size() == 1)
            cerr << "correct" << endl;
        else
            cerr << "ono" << endl;
    }
#endif
    return 0;
}

Details

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 30
Accepted
time: 0ms
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: 0ms
memory: 1668kb

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

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

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: 3ms
memory: 1324kb

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: 1ms
memory: 1368kb

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

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

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: -30
Wrong Answer
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:

no

result:

wrong answer participant output is not correct

Subtask #2:

score: 30
Accepted

Test #11:

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

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

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

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

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

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

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

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:

lllllllrrlllllllllrlllllllllllllllllllllllllllllll

result:

ok ok

Test #18:

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

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

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: 2ms
memory: 2580kb

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:

lllllllllllllllllllllllllllllllrllllllrrllllllllll

result:

ok ok

Subtask #3:

score: 40
Accepted

Test #21:

score: 40
Accepted
time: 40ms
memory: 127940kb

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:

lllllllllllllllllllllllrllllllllllllllllllllllllllllllllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

result:

ok ok

Test #22:

score: 0
Accepted
time: 41ms
memory: 112652kb

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:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok

Test #23:

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

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:

lllllllllllllllllllllllllllllllllllllllllllllllllllrllllllllrlllrlllllllllllllllllllllllrrllllllrrll...

result:

ok ok

Test #24:

score: 0
Accepted
time: 51ms
memory: 133352kb

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:

lllllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllllrllllrrrllrlrrrrrrrrrrrrrrrrrrllllllllrllllllllll...

result:

ok ok

Test #25:

score: 0
Accepted
time: 56ms
memory: 102048kb

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:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok

Test #26:

score: 0
Accepted
time: 31ms
memory: 129432kb

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:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok

Test #27:

score: 0
Accepted
time: 60ms
memory: 151636kb

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: 20ms
memory: 90988kb

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:

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllrrrllllrllrrllrrrlllrrrrrrr...

result:

ok ok

Test #29:

score: 0
Accepted
time: 29ms
memory: 83376kb

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: 36ms
memory: 144708kb

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:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

result:

ok ok