QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #868050 | #9684. 倾诉 | le0n | 0 | 3344ms | 16584kb | C++20 | 7.7kb | 2025-01-24 11:28:46 | 2025-01-24 11:28:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4 + 5, B = 20;
const int mod[3] = {998244353, (int)1e9 + 7, (int)1e9 + 9}, inf = (int)1e9 + 5;
int pw[3][N];
int sum[3][N];
int val[N][35], mx[N], pos[N], a[N], n;
int qry(int l, int r)
{
if(r - l <= B)
return val[r][r - l];
return mx[r] - (l > pos[r]);
}
struct node
{
int l, r, k;
node(int l0 = 0, int r0 = 0, int k0 = 0)
{
l = l0;
r = r0;
k = k0;
}
int qval()
{
return qry(l, r) >> k;
}
int qbit(int x)
{
x -= k;
if(x < 0)
return (qry(l, r) >> (-x)) & 1;
if(x > r - l)
return 0;
return qry(l, r - x) & 1;
}
vector<int> hs(int x)
{
int i;
x -= k;
if(x < 0)
{
int v = qry(l, r) >> (-x);
return {v, v, v};
}
vector<int> ans;
if(x > r - l)
{
for(i = 0; i < 3; i++)
ans.emplace_back((sum[i][l] + (ll)(mod[i] - pw[i][r - l + 1]) * sum[i][r + 1]) % mod[i] * pw[i][x - r + l] % mod[i]);
return ans;
}
for(i = 0; i < 3; i++)
ans.emplace_back((qry(l, r - x) + 2 * (sum[i][r - x + 1] + (ll)(mod[i] - pw[i][x]) * sum[i][r + 1])) % mod[i]);
return ans;
}
};
bool chk(node A, node B) // A < B
{
int lim = n + 30;
if(A.hs(lim) == B.hs(lim))
return make_pair(make_pair(A.l, A.r), A.k) < make_pair(make_pair(B.l, B.r), B.k);
// printf("A\n");
if(A.qval() != B.qval())
return A.qval() < B.qval();
// printf("B\n");
int l, r, mid;
l = 1;
r = lim;
while(l <= r)
{
mid = (l + r) >> 1;
// printf("PP%d %d %d\n", mid, A.hs(mid)[0], B.hs(mid)[0]);
if(A.hs(mid) == B.hs(mid))
l = mid + 1;
else
r = mid - 1;
}
// printf("OO%d %d %d\n", l, A.qbit(l), B.qbit(l));
return A.qbit(l) < B.qbit(l);
}
ll dp[N][35];
int lp[N][35], L[N][35], R[N][35];
ll mxv[21][N];
node ans;
vector<int> out;
int main()
{
mt19937_64 rng(123823);
int T, k, i, j, p, fl, l, r, mid;
ll tmp, tot, x;
node qwq;
n = 3e4;
for(j = 0; j < 3; j++)
{
pw[j][0] = 1;
for(i = 1; i <= n; i++)
pw[j][i] = 2ll * pw[j][i - 1] % mod[j];
}
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &k);
for(i = 1; i <= n; i++)
scanf("%d", a + i);
for(j = 0; j < 3; j++)
{
sum[j][n + 1] = 0;
for(i = n; i >= 1; i--)
sum[j][i] = (2ll * sum[j][i + 1] + a[i]) % mod[j];
}
for(i = 1; i <= n; i++)
{
tmp = 0;
memset(val[i], 0, sizeof(val[i]));
mx[i] = pos[i] = 0;
for(j = i; j >= max(i - B, 1); j--)
{
tmp = 2 * tmp + a[j];
val[i][i - j] = (tmp >> (i - j));
if(val[i][i - j] > mx[i])
{
mx[i] = val[i][i - j];
pos[i] = j;
}
}
if(mx[i - 1] / 2 + a[i] > mx[i])
{
mx[i] = mx[i - 1] / 2 + a[i];
pos[i] = pos[i - 1];
}
}
// for(i = 1; i <= n; i++)
// for(j = i; j <= n; j++)
// printf("??%d %d %d\n", i, j, qry(i, j));
ans = node(n, n, -1);
tot = 0;
for(i = 1; i <= n; i++)
for(j = 0; j <= B; j++)
{
L[i][j] = 1;
R[i][j] = i;
tot += R[i][j] - L[i][j] + 1;
}
// printf("#%d\n", chk(node(1, 1, 1), node(6, 9, 0)));
// return 0;
while(tot)
{
x = rng() % tot + 1;
fl = 0;
qwq = node(n, n, -1);
for(i = 1; i <= n; i++)
{
for(j = 0; j <= B; j++)
if(x <= R[i][j] - L[i][j] + 1)
{
fl = 1;
qwq = node(L[i][j] - 1 + x, i, j);
break;
}
else
x -= max(R[i][j] - L[i][j] + 1, 0);
if(fl)
break;
}
for(i = 1; i <= n; i++)
for(j = 0; j <= B; j++)
if(i == qwq.r && j == qwq.k)
lp[i][j] = qwq.l;
else
{
l = 1;
r = i;
while(l <= r)
{
mid = (l + r) >> 1;
if(chk(node(mid, i, j), qwq))
r = mid - 1;
else
l = mid + 1;
}
lp[i][j] = l;
}
// printf("#%lld %d %d %d\n", tot, qwq.l, qwq.r, qwq.k);
// for(i = 1; i <= n; i++)
// for(j = 0; j <= B; j++)
// printf("!!%d %d: %d %d %d\n", i, j, L[i][j], R[i][j], lp[i][j]);
// return 0;
for(i = 0; i <= B; i++)
dp[0][i] = 0;
for(i = 1; i <= n; i++)
{
for(j = 0; j <= B; j++)
{
dp[i][j] = (j ? dp[i][j - 1] : inf);
if(lp[i][j] >= i - B)
{
for(p = i; p >= lp[i][j]; p--)
dp[i][j] = min(dp[i][j], dp[p - 1][min(j + i - p, B)] + j + i - p);
continue;
}
for(p = i; p >= i - B; p--)
dp[i][j] = min(dp[i][j], dp[p - 1][min(j + i - p, B)] + j + i - p);
// for(p = i - B - 1; p >= lp[i][j]; p--)
// dp[i][j] = min(dp[i][j], dp[p - 1][B] + j + i - p);
int Lp = lp[i][j], Rp = i - B - 1;
int oo = __lg(Rp - Lp + 1);
dp[i][j] = max(dp[i][j], max(mxv[oo][Rp], mxv[oo][Lp + (1 << oo) - 1]) + j + i);
}
mxv[0][i] = dp[i - 1][B] - i;
for(j = 1; j <= __lg(i); j++)
mxv[j][i] = max(mxv[j - 1][i], mxv[j - 1][i - (1 << (j - 1))]);
}
if(dp[n][0] <= k)
{
ans = qwq;
for(i = 1; i <= n; i++)
for(j = 0; j <= B; j++)
L[i][j] = max(L[i][j], lp[i][j] + (i == qwq.r && j == qwq.k));
}
else
for(i = 1; i <= n; i++)
for(j = 0; j <= B; j++)
R[i][j] = min(R[i][j], lp[i][j] - 1);
tot = 0;
for(i = 1; i <= n; i++)
for(j = 0; j <= B; j++)
tot += max(R[i][j] - L[i][j] + 1, 0);
}
// printf("#%d %d %d\n", ans.l, ans.r, ans.k);
out.clear();
p = n - ans.k - ans.r + ans.l;
while(p--)
out.emplace_back(0);
tmp = 0;
for(i = ans.l; i <= ans.r; i++)
{
if(i > ans.l)
out.emplace_back(tmp & 1);
tmp = tmp / 2 + a[i];
}
while(tmp)
{
out.emplace_back(tmp & 1);
tmp /= 2;
}
reverse(out.begin(), out.end());
for(auto o: out)
printf("%d", o);
printf("\n");
// return 0;
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 2
Accepted
time: 2ms
memory: 16328kb
input:
5 6 1 11764 28428 28179 18698 6443 20288 6 3 29 17548 61962 31242 8172 4107 6 15 7 2 239427 137145 171239 3 6 4 294 211 407 190 2 2 6 5 197190 265870 12121 144584 21313 14169
output:
110111100001100000000 101110011000100110000 11101001110100001100000 11000110110000 10100110100010001101100
result:
ok 5 lines
Test #2:
score: 2
Accepted
time: 4ms
memory: 16572kb
input:
3 10 9 11333 23 34461 34357 354 4 3 55 3 3 10 13 5 17524 48186 2193 17524 17524 20914 15829 17524 6 10 5 128279 27396 7992 44204 132529 84302 26783 3378 42535 3786
output:
11010110100011011110 101111000011101000000000 11010100100010110010000000
result:
ok 3 lines
Test #3:
score: 0
Wrong Answer
time: 3ms
memory: 16156kb
input:
1 30 23 129534 106530 312047 478493 635175 682687 771242 851161 898940 103771 4 22344 668706 758190 219263 803071 787124 804602 997769 398659 874234 1 845912 226469 600617 203296 540318 171121 5 103637
output:
110010100110101010000000000000000000000000000000
result:
wrong answer 1st lines differ - expected: '1011110001001010101000000000000000000000000000000', found: '110010100110101010000000000000000000000000000000'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #60:
score: 17
Accepted
time: 605ms
memory: 16540kb
input:
1666 6 1 282 719 29 355 388 275 6 1 348 766 91 299 474 96 6 23 5 2 8554 8554 8554 2 6 1 84 195 23 37 120 117 6 3 8 3 51 62 28 5 6 3 3 64 64 4 4 2 6 9 5 552 552 552 552 5 6 3 3611 1144 417 3461 459 755 6 3 777 315 1007 5 2 1061 6 6 1300 2101 4 1877 360 2434 6 1 384 713 168 25 524 390 6 3 203 18 305 1...
output:
110000100100000 111011010000000 1000010110111000000 1111000100000 11111000000 11110000000 100011001000000 100010001101100000 10000100101000000 100110000010000000 1000001100100000 10011001100000 111001011010000000 1100000110100000 1110111111110000 101011111000000 1000011110000 100101000000000 1011110...
result:
ok 1666 lines
Test #61:
score: 17
Accepted
time: 915ms
memory: 16576kb
input:
1000 10 10 1765 725 287 2983 1959 3 855 1094 2960 4 10 4 856 92 85 15 31 233 718 137 64 213 10 8 4575 2773 2373 497 8150 5057 2455 9107 5 5 10 8 216 189 143 218 154 222 153 147 2 5 10 3 77 74 30 27 241 85 57 8 66 86 10 7 3471 3468 5868 2881 478 3775 2 470 1 3 10 5 317 2460 139 3033 107 359 4 1716 3 ...
output:
101110011000000000000 1010110010000000000 1100010110011110000000 11011110000000000 10101111110000000 110110001111000000000 100100100101100000000 1101111101000000000 10111010010110000000 1111110111101100 10100101000100000000 10100110000110000000 1011110110101000000000 10011110100000000000 10000100100...
result:
ok 1000 lines
Test #62:
score: 0
Wrong Answer
time: 1192ms
memory: 16584kb
input:
400 25 16 678 1005 3339 2086 1363 1802 549 124 406 305 325 742 3344 2194 640 2744 383 1494 2369 1209 667 120 423 243 91 25 16 5 6 5 4 4 37 6 2 2 2 2 2 2 2 2 7 13 12 9 10 15 32 32 1 4 25 18 848 963 139 413 186 82 1329 524 629 70 40 324 1255 282 581 193 439 189 81 268 769 733 22 36 332 25 23 61 41 39 ...
output:
101101100000000000000000000000000 10000000000000000000000000000 1101111110010000000000000000000000 110110010001110110001100000 1110011010011000000000000000000000000 11000001001110000000000000000000000 10000000000000000000000000000 10100000000000000000000000000 110011000000000000000000000000000 11000...
result:
wrong answer 1st lines differ - expected: '11111011010000000000000000000000000', found: '101101100000000000000000000000000'
Subtask #6:
score: 0
Time Limit Exceeded
Test #80:
score: 16
Accepted
time: 1159ms
memory: 16572kb
input:
3333 6 1000000000 131727 7 4 170194 6 59263 6 1000000000 417714 286613 7 310122 6 4 6 1000000000 63764 2430 2696 6699 8478 22261 6 1000000000 217 131 6 1487 2927 2 6 1000000000 26225 27991 3842 72525 4521 5231 6 1000000000 34409 26001 23563 19345 30764 24919 6 1000000000 97981 138532 59280 82393 128...
output:
10100110001101001000000 10010111011100001100000 101011011110101000000 10110111001100000 110010000010110110000 111100110010110100000 11111011000100010000000 11001111100101100 1100000101001001010100000 100000000000 100111000110001000000 101110110010100111000000 10000000000000000000000 1100000111101000...
result:
ok 3333 lines
Test #81:
score: 16
Accepted
time: 1760ms
memory: 16560kb
input:
2000 10 1000000000 4 225227 95031 258432 108444 260818 190505 154686 1 5 10 1000000000 541067 480522 7 372550 533382 366492 200177 240412 6 1 10 1000000000 10004 14230 86468 2812 9690 7106 21976 45928 9749 30567 10 1000000000 12217 2718 4247 9981 12911 1845 2048 4 1387 16384 10 1000000000 46966 1438...
output:
11110100000110100010000000 101001100100010010010000000 1111111110010010000000000 1000000000000000000000000 11010100011000000000 110010110111010010100000000 11000010111011011011000000000 1001001110000111010000000000 11110110001100100100000000 101110111011100111000000000 100001001101001011110000000 10...
result:
ok 2000 lines
Test #82:
score: 16
Accepted
time: 3344ms
memory: 16564kb
input:
800 25 1000000000 87944 70771 86657 342502 146802 122800 216223 248367 121688 22026 9518 1128 64025 63379 231058 292954 218186 35314 64373 10501 20550 32081 39386 10095 78181 25 1000000000 54665 3 129508 98607 92526 68177 57466 62726 21642 52766 23748 16110 18286 9033 4 6 3 6 2 5 7 5 7 1 4 25 100000...
output:
100110001011001010000000000000000000000000 11001101110010100000000000000 1101110010100110110000000000000000000000 1011101001000100000000000000000000000000 10100110000000000000000000000000 1001111010011010010000000000000000000000 10010000010110010011000000000000000000000000 10000010010000000000000000...
result:
ok 800 lines
Test #83:
score: 0
Time Limit Exceeded
input:
400 50 1000000000 36192 37096 41075 279152 132449 170424 203877 76049 163616 193360 220325 66999 100454 253404 184659 123538 175852 228265 36430 14534 5082 24007 9240 14589 22365 47490 42236 267799 144852 218552 99653 6256 50634 80363 90985 168540 213317 114099 2231 11664 17529 37776 44616 44454 102...
output:
11010001010111010000000000000000000000000000000000000000000000000 1100100111001001000000000000000000000000000000000000000000000000 100011011111111110000000000000000000000000000000000000000000000000 111000010111000000000000000000000000000000000000000000000000 11010001100000000000000000000000000000000...
result:
Subtask #7:
score: 0
Skipped
Dependency #4:
0%