QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #868043 | #9684. 倾诉 | le0n | 2 | 3343ms | 16580kb | C++20 | 7.8kb | 2025-01-24 11:26:29 | 2025-01-24 11:26:38 |
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], lg[N];
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(i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
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]));
}
mxv[0][i] = dp[i][B] - i - 1;
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: 2
Accepted
Test #1:
score: 2
Accepted
time: 3ms
memory: 12484kb
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: 2ms
memory: 14232kb
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: 2
Accepted
time: 6ms
memory: 14532kb
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:
1011110001001010101000000000000000000000000000000
result:
ok single line: '1011110001001010101000000000000000000000000000000'
Test #4:
score: 2
Accepted
time: 7ms
memory: 14548kb
input:
1 30 20 24369 112417 273642 91342 16920 82890 51488 110843 350768 2127 32310 317716 289575 345557 10461 133151 237824 131339 154529 77796 16773 128740 561207 292189 244465 178375 50425 149932 60698 32020
output:
100000110011011000011001110000000000000000000000
result:
ok single line: '100000110011011000011001110000000000000000000000'
Test #5:
score: 2
Accepted
time: 4ms
memory: 14540kb
input:
1 30 22 5164 3437 1409 1477 1234 290 641 8387 2389 4783 1704 1430 2859 422 368 348 3778 2161 1898 964 357 763 380 3870 6050 1136 3613 1747 975 131
output:
11100100111010100100000000000000000000000
result:
ok single line: '11100100111010100100000000000000000000000'
Test #6:
score: 2
Accepted
time: 10ms
memory: 14540kb
input:
1 30 16 78284 104679 51060 38372 468848 144187 84013 249991 72147 295666 63152 22000 35446 88085 67085 19719 4766 988 384917 450684 101500 548119 105206 420503 54774 10663 13882 48365 104067 33372
output:
11100010001001000011101010000000000000000000000
result:
ok single line: '11100010001001000011101010000000000000000000000'
Test #7:
score: 2
Accepted
time: 4ms
memory: 14464kb
input:
1 30 20 93587 95074 833612 98114 468073 405234 294453 151570 336309 555067 71292 497114 301076 302914 130800 17777 145963 834497 152338 526181 242311 266037 315170 36843 72099 59791 95401 96269 181758 156382
output:
111011010101101111000000101010000000000000000000
result:
ok single line: '111011010101101111000000101010000000000000000000'
Test #8:
score: 2
Accepted
time: 5ms
memory: 14532kb
input:
1 30 20 7 5 5 2 5 2 4 2 1 8 244222 244222 244222 244222 244222 244222 244222 244222 244222 244222 244222 244222 244222 244222 244222 244222 8 6 8 1
output:
111011101000110110010001100000001000000000000
result:
ok single line: '111011101000110110010001100000001000000000000'
Test #9:
score: 2
Accepted
time: 7ms
memory: 14548kb
input:
1 30 30 1486 898 1035 2327 2777 3385 4083 330 2925 3348 1324 826 3223 3418 45 184 54 591 44 4301 4453 1558 601 1914 2114 8 1 93 7 6
output:
10011001000001011100000000000000000000
result:
ok single line: '10011001000001011100000000000000000000'
Test #10:
score: 2
Accepted
time: 11ms
memory: 14540kb
input:
1 30 132 999998 999998 999999 999999 1000000 1000000 1000000 1000000 999999 1000000 999999 1000000 999998 999999 999999 999999 999998 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
10110111000110101111000000000000000000
result:
ok single line: '10110111000110101111000000000000000000'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #11:
score: 10
Accepted
time: 12ms
memory: 14528kb
input:
33 6 1 2201 30891 22926 51021 5381 1953 6 1 17621 35116 7069 5597 24627 4779 6 8 6 19015 19015 19015 19015 2 6 4 19047 11041 11837 2027 1116 2645 6 7 117530 117530 117530 117530 117530 4 6 5 26692 20497 5915 6516 6714 1098 6 7 348470 348470 348470 348470 348470 7 6 3 2 1 2378 4 107252 2 6 2 9325 369...
output:
111100010101011100000 110000000110011000000 10010100100101100000 1110111101011010100 1110010110010001000000 10001011101010100100 101010100010100010000000 1101000101111100000000 1001001101001001000000 10100110001010100000 1111111101011100000 1110110000100000000 1000010001100101000000 1010011111111001...
result:
ok 33 lines
Test #12:
score: 10
Accepted
time: 20ms
memory: 14528kb
input:
20 10 10 7398 2663 2 28570 2 2 2 2 2 3 10 10 5 4 486615 486615 486615 521695 469075 486615 486615 7 10 5 5132 160984 19067 83543 351799 157254 40607 16829 39349 21513 10 3 2234 2158 11383 7501 3047 737 626 4487 5017 4908 10 5 31661 111680 91073 9607 12095 42688 118218 47360 392 51408 10 3 28734 5994...
output:
1110111000011011000 1111111010111011111000000000 110000100111001110000000000 10101101101101010000000 11010001011110101100000000 111000110111001000000000000 11111011001001000000000000 11110011101111100000000 1000111111101100000000000 1110010101000111001000000000 11100111110110011100000 10110011111001...
result:
ok 20 lines
Test #13:
score: 0
Wrong Answer
time: 33ms
memory: 14548kb
input:
8 25 15 2317 3833 9894 20350 54995 518 77 9839 15551 281 5127 13100 16 13930 16 16 3872 44999 28972 30892 63777 36955 9212 13452 6 25 24 99488 111510 114067 99889 114169 167030 178257 168039 292710 214341 275210 350436 319813 436188 410390 450309 445475 482666 516698 666862 623999 693281 692643 7096...
output:
110110011010100000000000000000000000000 10101101010000100100000000000000000000000000 10011011101101000110000001000000 1000010011011111000000000000000000000 11111000000101000000000000000000000000000 10110110001100111011110110000000000000000 111010000000000000000000000000 10011010000011010101010000000...
result:
wrong answer 3rd lines differ - expected: '111001101011010001100000010000', found: '10011011101101000110000001000000'
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: 14492kb
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: 927ms
memory: 16580kb
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: 1771ms
memory: 14532kb
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:
11111011010000000000000000000000000 11001000000000000000000000000 1011111100101000000000000000000000 110110010001110110001100000 1100011111111100000000000000000000000 11000001001110000000000000000000000 110000110110000000000000000000000000 100110110000101000000000000000000 11010000111000000000000000...
result:
wrong answer 40th lines differ - expected: '10001011011111111111110111101100', found: '100001001111111110111101100000000'
Subtask #6:
score: 0
Time Limit Exceeded
Test #80:
score: 16
Accepted
time: 1139ms
memory: 14540kb
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: 1746ms
memory: 14492kb
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: 3343ms
memory: 14544kb
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%