QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #347668 | #6753. Medians | wtz2333 | AC ✓ | 327ms | 120456kb | C++17 | 1.7kb | 2024-03-09 14:45:54 | 2024-03-09 14:45:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mo = 998244353;
const int P = 1e9 + 7;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> p(n + 1),pre(n + 1),nxt(n + 1);
for (int i = 1; i <= n;i ++) {
p[i] = i;
pre[i] = i - 1;
nxt[i] = i + 1;
}
int a;
cin >> a;
for(int i = 1;i <= n;i ++) {
int x = (1ll * a * mo + P) % (P + 2);
swap(p[i],p[(x % i) + 1]);
a = x;
}
// vector<int> ans(n + 1);
int last = (n + 1) / 2;
int ans;
int Ans = last;
for(int i = n - 1;i >= 1;i --) {
if(p[i + 1] == last) {
if(i & 1) {
int x = last;
x = nxt[x];
ans = x;
}else {
int x = last;
x = pre[x];
ans = x;
}
}else if(p[i + 1] < last) {
if(i & 1) {
int x = last;
x = nxt[x];
ans = x;
}else ans = last;
}else {
if(i & 1) {
ans = last;
}else {
int x = last;
x = pre[x];
ans = x;
}
}
int x = p[i + 1];
if(pre[x] >= 0)nxt[pre[x]] = nxt[x];
if(nxt[x] <= n)pre[nxt[x]] = pre[x];
pre[x] = nxt[x] = -1;
Ans = (1ll * Ans * 19 % mo + ans) % mo;
last = ans;
}
cout << (1ll * Ans * 19) % mo << endl;
}
// n / 20210926 <= k
/// 1 2 3 4 5 6 7 8
// 14 5 2 2 1 1 1 1
// 13 4 1 1 0 0 0 0
// 12 3 0 0 0 0 0 0
//
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3668kb
input:
5 0
output:
7703113
result:
ok 1 number(s): "7703113"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 1
output:
7840977
result:
ok 1 number(s): "7840977"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
2 1361955
output:
399
result:
ok 1 number(s): "399"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 207579012
output:
274740
result:
ok 1 number(s): "274740"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
8 628145516
output:
783389330
result:
ok 1 number(s): "783389330"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
16 376140462
output:
772072366
result:
ok 1 number(s): "772072366"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
32 883515280
output:
822906393
result:
ok 1 number(s): "822906393"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
64 186969585
output:
536948870
result:
ok 1 number(s): "536948870"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
128 762888635
output:
914896632
result:
ok 1 number(s): "914896632"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
256 326402539
output:
816864808
result:
ok 1 number(s): "816864808"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
512 98152102
output:
792934555
result:
ok 1 number(s): "792934555"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1024 158176572
output:
187304261
result:
ok 1 number(s): "187304261"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2048 61402883
output:
881629018
result:
ok 1 number(s): "881629018"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
4096 127860889
output:
926052991
result:
ok 1 number(s): "926052991"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
8192 9580638
output:
18767865
result:
ok 1 number(s): "18767865"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
16384 570870044
output:
676635475
result:
ok 1 number(s): "676635475"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
32768 646139319
output:
121314798
result:
ok 1 number(s): "121314798"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
65536 178509022
output:
518784793
result:
ok 1 number(s): "518784793"
Test #19:
score: 0
Accepted
time: 3ms
memory: 4652kb
input:
131072 484027666
output:
783563468
result:
ok 1 number(s): "783563468"
Test #20:
score: 0
Accepted
time: 5ms
memory: 6212kb
input:
262144 61263304
output:
560815556
result:
ok 1 number(s): "560815556"
Test #21:
score: 0
Accepted
time: 10ms
memory: 9196kb
input:
524288 841082555
output:
478037004
result:
ok 1 number(s): "478037004"
Test #22:
score: 0
Accepted
time: 16ms
memory: 15684kb
input:
1048576 558212774
output:
145045199
result:
ok 1 number(s): "145045199"
Test #23:
score: 0
Accepted
time: 34ms
memory: 27872kb
input:
2097152 940563715
output:
267114566
result:
ok 1 number(s): "267114566"
Test #24:
score: 0
Accepted
time: 80ms
memory: 52480kb
input:
4194304 26389620
output:
535216368
result:
ok 1 number(s): "535216368"
Test #25:
score: 0
Accepted
time: 244ms
memory: 101332kb
input:
8388608 579113528
output:
926081338
result:
ok 1 number(s): "926081338"
Test #26:
score: 0
Accepted
time: 287ms
memory: 120216kb
input:
10000000 496147999
output:
872799419
result:
ok 1 number(s): "872799419"
Test #27:
score: 0
Accepted
time: 312ms
memory: 120304kb
input:
10000000 925801172
output:
676521567
result:
ok 1 number(s): "676521567"
Test #28:
score: 0
Accepted
time: 299ms
memory: 120348kb
input:
10000000 837151740
output:
617759049
result:
ok 1 number(s): "617759049"
Test #29:
score: 0
Accepted
time: 327ms
memory: 120392kb
input:
10000000 70301164
output:
413391579
result:
ok 1 number(s): "413391579"
Test #30:
score: 0
Accepted
time: 285ms
memory: 120300kb
input:
10000000 656585275
output:
505441893
result:
ok 1 number(s): "505441893"
Test #31:
score: 0
Accepted
time: 302ms
memory: 120456kb
input:
10000000 285845005
output:
465986348
result:
ok 1 number(s): "465986348"
Test #32:
score: 0
Accepted
time: 301ms
memory: 120300kb
input:
10000000 902071050
output:
964328151
result:
ok 1 number(s): "964328151"