ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215349 | #2777. 2048 | N | 70 | 425ms | 151636kb | C++11 | 4.8kb | 2024-11-28 20:24:07 | 2024-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