QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #519744 | #5100. 卡牌游戏 | SunsetGlow95 | 0 | 63ms | 36556kb | C++14 | 3.2kb | 2024-08-15 00:57:15 | 2024-08-15 00:57:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int read() {
int x(0), c(getchar());
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
return x;
}
using ll = long long;
const int MXN = 500005;
const int FB = 800;
const int MXLG = 20;
int N, S, B, arr[MXN], agcd[FB][FB], bis[MXN], bid, pos[MXN][2], lg2[MXN];
ll pv[MXN], sv[MXN], mxp[MXN], tag[MXLG][MXN], ans;
inline int cal(int a, int b) {
return S - S % (a / agcd[a][b % a] * 1LL * b);
}
template<typename T>
inline void chkmx(T& a, T b) { if (a < b) a = b; }
inline void add(int l, int r, ll v) {
if (l == r) return;
int len(lg2[r - l]);
chkmx(tag[len][l], v);
chkmx(tag[len][r - (1 << len)], v);
}
int main() {
N = read(), S = read();
B = sqrt(S) + 1;
for (int i(0); i != B; ++i)
agcd[i][0] = agcd[0][i] = i;
for (int i(1); i != B; ++i)
for (int j(i); j != B; ++j)
agcd[j][i] = agcd[i][j] = agcd[i][j - i];
lg2[1] = 0;
for (int i(2); i <= N; ++i) lg2[i] = lg2[i >> 1] + 1;
for (int i(0); i != N; ++i) {
arr[i] = read();
if (arr[i] < B) bis[bid++] = i;
}
memset(mxp, 0xc0, sizeof mxp);
for (int i(0), it(0); i != N; ++i) {
if (i) chkmx(pv[i], pv[i - 1]);
while (it != bid && bis[it] < i) ++it;
for (int d(1); d <= 3 && d <= it; ++d)
chkmx(pv[i], pv[bis[it - d]] + cal(arr[bis[it - d]], arr[i]));
if (arr[i] >= B) {
for (int j(arr[i]); j <= S; j += arr[i]) chkmx(pv[i], mxp[j] + S - S % j);
for (int j(arr[i]); j <= S; j += arr[i]) chkmx(mxp[j], pv[i]);
}
for (int d(bis[it] == i); d <= 3 && it + d < bid; ++d) {
chkmx(pv[bis[it + d]], pv[i] + cal(arr[bis[it + d]], arr[i]));
}
}
cout << pv[N - 1] << ' ';
memset(mxp, 0xc0, sizeof mxp);
memset(pos, -1, sizeof pos);
reverse(bis, bis + bid);
for (int i(N - 1), it(0); ~i; --i) {
if (i + 1 < N) chkmx(sv[i], sv[i + 1]);
while (it != bid && bis[it] > i) ++it;
for (int d(1); d <= 3 && d <= it; ++d) {
chkmx(sv[i], sv[bis[it - d]] + cal(arr[bis[it - d]], arr[i]));
add(i + 1, bis[it - d], pv[i] + sv[bis[it - d]] + cal(arr[bis[it - d]], arr[i]));
}
if (arr[i] >= B) {
for (int j(arr[i]); j <= S; j += arr[i]) {
chkmx(sv[i], mxp[j] + S - S % j);
if (pos[j][0] != -1)
add(i + 1, pos[j][0], pv[i] + mxp[j] + S - S % j);
if (pos[j][1] != -1)
chkmx(tag[0][pos[j][0]], pv[i] + sv[pos[j][1]] + S - S % j);
}
for (int j(arr[i]); j <= S; j += arr[i]) {
if (mxp[j] <= sv[i]) pos[j][1] = pos[j][0], pos[j][0] = i, mxp[j] = sv[i];
}
}
for (int d(bis[it] == i); d <= 3 && it + d < bid; ++d) {
chkmx(sv[bis[it + d]], sv[i] + cal(arr[bis[it + d]], arr[i]));
add(bis[it + d] + 1, i, pv[bis[it + d]] + sv[i] + cal(arr[bis[it + d]], arr[i]));
}
assert(sv[i] + pv[i] <= pv[N - 1]);
}
for (int i(lg2[N]); i; --i)
for (int j(0); j + (1 << i) <= N; ++j)
chkmx(tag[i - 1][j], tag[i][j]), chkmx(tag[i - 1][j + (1 << (i - 1))], tag[i][j]);
for (int i(0); i != N; ++i) {
chkmx(tag[0][i], (i ? pv[i - 1] : 0) + (i + 1 < N ? sv[i + 1] : 0));
ans ^= tag[0][i];
}
cout << ans << endl;
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 20868kb
input:
1000 100000 1 1 69 99 297 63 277 271 109 268 209 181 100 195 282 137 211 270 87 10 247 294 138 108 33 258 152 265 304 154 201 66 269 189 5 162 134 276 144 187 107 170 16 135 253 67 156 138 299 165 70 258 158 239 186 168 277 261 86 173 153 14 35 226 158 258 129 152 295 235 271 31 192 92 153 236 142 1...
output:
91048303 486949
result:
wrong answer 1st numbers differ - expected: '91045064', found: '91048303'
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 22284kb
input:
10000 100000 1 2 91 50 303 100 42 100 36 306 191 90 99 45 196 144 64 35 98 147 180 115 16 209 62 315 270 295 26 60 139 135 98 39 148 7 239 133 268 218 179 225 253 289 289 279 31 244 288 68 128 275 147 2 222 146 303 215 51 212 84 4 64 183 153 58 230 13 34 58 45 237 301 303 241 92 140 306 60 83 273 23...
output:
913814161 128021
result:
wrong answer 1st numbers differ - expected: '913775751', found: '913814161'
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 32ms
memory: 35272kb
input:
100000 300000 1 3 274679 257449 79355 22007 205440 219549 7516 102115 226913 157081 9451 228050 8862 198356 270934 221218 162391 221194 235433 234134 70219 45552 211652 248648 164511 74601 168682 139466 189586 258255 264158 218369 21734 195969 71728 299881 104633 21390 36649 25670 121247 41503 20806...
output:
226708945 296378
result:
wrong answer 1st numbers differ - expected: '226109485', found: '226708945'
Subtask #4:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 10ms
memory: 24112kb
input:
100000 300000 1 4 22 98 92 49 86 56 11 69 100 65 99 79 39 97 40 88 47 28 79 43 75 13 43 41 69 56 62 47 21 28 69 95 1 92 92 60 78 15 3 20 96 15 95 82 38 9 80 26 64 21 19 48 17 27 79 7 25 66 100 70 94 16 21 61 13 57 42 60 66 18 99 97 69 63 89 20 73 22 64 41 19 9 9 45 64 97 4 71 41 93 65 49 81 23 4 52 ...
output:
29908227685 129732
result:
wrong answer 1st numbers differ - expected: '29908227273', found: '29908227685'
Subtask #5:
score: 0
Runtime Error
Test #19:
score: 0
Runtime Error
input:
100000 100000 0 5 160 79 241 305 285 252 135 178 99 105 215 136 248 256 255 309 149 226 295 99 253 269 40 126 95 232 201 201 275 306 119 314 91 222 89 135 62 240 100 178 274 99 107 278 238 193 222 311 218 242 46 74 180 253 141 100 33 54 267 90 274 199 64 279 132 183 135 266 258 208 169 89 194 114 11...
output:
result:
Subtask #6:
score: 0
Wrong Answer
Test #26:
score: 0
Wrong Answer
time: 11ms
memory: 23636kb
input:
100000 100000 1 6 99 254 235 123 310 237 248 278 100 34 213 275 66 242 297 120 272 185 140 149 276 165 163 162 119 142 79 6 66 163 134 296 176 12 45 96 152 200 59 127 279 249 67 111 208 49 161 121 153 72 280 164 310 266 228 23 101 197 88 245 32 23 51 140 206 112 207 164 207 40 262 245 224 258 167 15...
output:
9115721515 57440
result:
wrong answer 1st numbers differ - expected: '9115701137', found: '9115721515'
Subtask #7:
score: 0
Runtime Error
Test #33:
score: 0
Runtime Error
input:
300000 300000 0 7 101 52 102 151 14 514 86 100 239 399 486 520 239 489 176 112 517 478 215 539 134 46 200 54 307 48 78 220 205 433 509 312 381 13 457 515 481 223 326 300 193 103 289 203 393 25 506 137 7 239 201 343 165 107 135 487 16 162 177 369 415 246 59 169 127 522 207 465 418 287 311 248 298 311...
output:
result:
Subtask #8:
score: 0
Wrong Answer
Test #40:
score: 0
Wrong Answer
time: 43ms
memory: 29976kb
input:
300000 300000 1 8 404 482 307 14 397 186 112 173 197 389 278 419 417 196 138 264 161 330 395 465 84 516 235 507 515 247 222 268 105 119 435 328 514 337 356 246 204 370 364 174 512 538 129 135 203 348 247 58 430 238 165 397 203 145 175 435 158 297 443 446 467 3 493 294 394 375 157 405 385 449 116 361...
output:
82044765054 311034
result:
wrong answer 1st numbers differ - expected: '82044763846', found: '82044765054'
Subtask #9:
score: 0
Runtime Error
Test #47:
score: 0
Runtime Error
input:
500000 500000 0 9 464 653 212 650 549 203 500 292 366 468 464 660 240 393 279 587 405 403 148 638 438 251 441 92 302 270 56 271 559 639 474 193 644 310 48 548 559 289 163 439 372 425 121 459 620 636 282 610 133 283 215 317 451 166 431 21 139 229 261 260 9 112 71 468 287 312 680 330 95 140 92 44 238 ...
output:
result:
Subtask #10:
score: 0
Wrong Answer
Test #54:
score: 0
Wrong Answer
time: 63ms
memory: 36556kb
input:
500000 500000 1 10 508 318 336 300 675 515 168 520 687 644 236 670 590 176 478 99 119 556 430 385 117 89 483 321 194 194 314 236 438 142 18 499 161 495 649 255 190 667 396 600 165 376 547 145 390 43 485 645 32 685 54 276 322 353 659 516 102 440 476 351 282 94 222 594 98 399 22 434 50 76 84 504 2 173...
output:
227911508304 1897037
result:
wrong answer 1st numbers differ - expected: '227911469762', found: '227911508304'