ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215351 | #2777. 2048 | KXG | 0 | 0ms | 0kb | C++11 | 3.5kb | 2024-11-28 20:30:24 | 2024-11-28 23:11:55 |
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)); 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) | 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);
}
if (nxtS1 >= (1 << p) || nxtS2 >= (1 << p)) {
anslst = (S << 1);
}
dp[(nxtS1 << p) | 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);
}
if (nxtS1 >= (1 << p) || nxtS2 >= (1 << p)) {
anslst = (S << 1) | 1;
}
dp[(nxtS1 << p) | 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: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
20 2 8 8 256 2 32 64 64 2 2 64 8 256 128 128 1024 2048 2048 1024 1024
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
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:
result:
Subtask #3:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
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...