NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #215354 | #2777. 2048 | KXG | 30 | 819ms | 132244kb | C++11 | 3.9kb | 2024-11-28 20:35:38 | 2024-11-28 23:12:05 |
answer
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
int n, p, a[10010], s[10010];
int pos[10010];
int dp[35000010];
unsigned highbit(unsigned i) {
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i |= i >> 32;
return (i + 1) >> 1;
}
unsigned lowbit(unsigned i) {
return i & (-i);
}
int getnxt(int S, int x) {
if (S != 0 && lowbit(S) < x) {
return -1;
}
S += x;
if (S >= (1 << p)) return -2;
return S;
}
int main() {
memset(pos, -1, sizeof(pos));
scanf("%d", &n);
pos[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
pos[s[i]] = i;
}
p = log2(s[n]);
if (s[n] != (1 << p)) {
printf("no\n");
return 0;
}
if (n == 1) {
printf("l\n");
return 0;
}
for (int S = 0; S < (1 << (2 * p - 1)); S++) {
dp[S] = -1;
}
dp[0] = 0;
int anslst = -1;
for (int S1 = 0; S1 < (1 << p); S1++) {
for (int S2 = 0; S1 + S2 < (1 << p) && S2 <= (1 << (p - 1)); S2++) {
if (pos[S1 + S2] == -1 || (highbit(S1) == highbit(S2) && S1 != 0 && S2 != 0)) {
continue;
}
int S = (S1 << (p - 1)) | S2;
if (dp[S] == -1) continue;
// printf("%d %d : %d\n", S1, S2, dp[S]);
int ps = pos[S1 + S2];
int nxtS1, nxtS2;
nxtS1 = getnxt(S1, a[ps + 1]);
nxtS2 = S2;
// printf("%d %d : %d %d\n", S1, S2, nxtS1, nxtS2);
if (nxtS1 != -1) {
if (nxtS1 == -2) {
anslst = (S << 1);
} else {
if (highbit(nxtS1) == highbit(nxtS2)) {
int x = highbit(nxtS1);
nxtS1 ^= x;
nxtS2 ^= x;
nxtS1 ^= (x << 1);
} else if (highbit(nxtS2) > highbit(nxtS1)) {
int x = highbit(nxtS2);
nxtS1 ^= x;
nxtS2 ^= x;
}
if (nxtS1 >= (1 << p) || nxtS2 >= (1 << p)) {
anslst = (S << 1);
}
dp[(nxtS1 << (p - 1)) | nxtS2] = (S << 1);
}
}
nxtS1 = S1;
nxtS2 = getnxt(S2, a[ps + 1]);
// printf("%d %d : %d %d\n", S1, S2, nxtS1, nxtS2);
if (nxtS2 != -1) {
if (nxtS2 == -2) {
anslst = (S << 1) | 1;
} else {
if (highbit(nxtS1) == highbit(nxtS2)) {
int x = highbit(nxtS1);
nxtS1 ^= x;
nxtS2 ^= x;
nxtS1 ^= (x << 1);
} else if (highbit(nxtS2) > highbit(nxtS1)) {
int x = highbit(nxtS2);
nxtS1 ^= x;
nxtS2 ^= x;
}
if (nxtS1 >= (1 << p) || nxtS2 >= (1 << p)) {
anslst = (S << 1) | 1;
}
dp[(nxtS1 << (p - 1)) | nxtS2] = (S << 1) | 1;
}
}
}
}
if (anslst == -1) {
printf("no\n");
} else {
vector<int> ans;
int now = anslst;
while (true) {
ans.push_back(now & 1);
now >>= 1;
if (now == 0) {
break;
}
now = dp[now];
}
for (int i = ans.size() - 1; i >= 0; i--) {
if (ans[i] == 0) {
printf("l");
} else {
printf("r");
}
}
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 35ms
memory: 132160kb
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: 35ms
memory: 132164kb
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: 36ms
memory: 132164kb
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: 31ms
memory: 132228kb
input:
20 1 1 2 2 2 8 16 64 32 128 512 128 128 512 512 1024 1024 2048 1024 1024
output:
rrrllrrrlrrlllllllll
result:
ok ok
Test #5:
score: 0
Accepted
time: 50ms
memory: 132164kb
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: 35ms
memory: 132164kb
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: 47ms
memory: 132164kb
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: 47ms
memory: 132164kb
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: 53ms
memory: 132224kb
input:
20 1 1 4 8 2 128 128 16 512 32 64 128 512 512 2048 512 256 256 1024 2048
output:
rrrrlrrlrlllllrlllll
result:
ok ok
Test #10:
score: 0
Accepted
time: 27ms
memory: 132160kb
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: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 50ms
memory: 132220kb
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:
rr
result:
wrong answer participant output is not valid
Subtask #3:
score: 0
Wrong Answer
Test #21:
score: 40
Accepted
time: 60ms
memory: 132240kb
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:
rrllllllllllllllllllllrlrrrrrrrrrlllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
result:
ok ok
Test #22:
score: 0
Accepted
time: 48ms
memory: 132244kb
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:
rrllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
result:
ok ok
Test #23:
score: 0
Accepted
time: 54ms
memory: 132244kb
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:
rrlllllllllllllllllllllllllllllllllllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrl...
result:
ok ok
Test #24:
score: 0
Accepted
time: 62ms
memory: 132240kb
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:
rrlllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllllllllllrrrrrrrrrrrrrrrrrrrrrrrr...
result:
ok ok
Test #25:
score: 0
Accepted
time: 51ms
memory: 132244kb
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:
rrllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
result:
ok ok
Test #26:
score: 0
Accepted
time: 43ms
memory: 132240kb
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:
rrllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
result:
ok ok
Test #27:
score: -40
Wrong Answer
time: 55ms
memory: 132244kb
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:
rlllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
result:
wrong answer participant output is not valid
