QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #637158 | #8285. Shell Sort | wangjunrui | AC ✓ | 1230ms | 63860kb | C++14 | 2.0kb | 2024-10-13 10:24:07 | 2024-10-13 10:24:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
static const long long mod = 1000000007;
static const int maxn = 30, maxm = 10;
int n, m;
static int d[maxm], msk[maxm][maxn];
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) scanf("%d", d + i);
int p = 0;
while (d[p] >= n) p++, m--;
for (int i = 0; i < m; i++) d[i] = d[i + p];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
int r = j % d[i], x = 0;
while (r < n) x ^= 1 << r, r += d[i];
msk[i][j] = x;
}
struct node {
int mx;
long long cnt;
inline node operator+(const node rhs) const {
return { max(mx, rhs.mx), ((mx >= rhs.mx) * cnt + (rhs.mx >= mx) * rhs.cnt) % mod };
}
};
function<node(const vector<int>&)> dfs = [&dfs, n, m](const vector<int>& v) {
static unordered_map<int, node> dp;
if (v[0] == (1 << n) - 1)
return (node){ 0, 1 };
if (dp.count(v[0]))
return dp[v[0]];
node ret = { 0, 0 };
for (int i = 0; i < d[0]; i++) {
int p = i + __builtin_popcount(v[0] & msk[0][i]) * d[0];
if (p >= n)
continue;
int cnt = 0;
auto nxt = v;
nxt[0] |= 1 << p;
for (int r = 1; r < m; r++) {
int s = nxt[r - 1] & msk[r][p];
cnt += __builtin_popcount(s >> p) - 1;
p = p % d[r] + (__builtin_popcount(s) - 1) * d[r];
nxt[r] |= 1 << p;
}
node cur = dfs(nxt);
cur.mx += cnt, ret = ret + cur;
}
return dp[v[0]] = ret;
};
int cnt = 0;
for (int i = 0; i < d[0]; i++) {
int pop = __builtin_popcount(msk[0][i]);
cnt += pop * (pop - 1) >> 1;
}
vector<int> v(m);
node ans = dfs(v);
ans.mx += cnt, printf("%d %lld\n", ans.mx, ans.cnt);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
8 4 6 3 2 1
output:
15 4
result:
ok 2 number(s): "15 4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
8 6 8 7 5 4 2 1
output:
14 2
result:
ok 2 number(s): "14 2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
8 1 1
output:
28 1
result:
ok 2 number(s): "28 1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 0
Accepted
time: 8ms
memory: 4400kb
input:
16 8 10 9 8 7 6 5 4 1
output:
57 5
result:
ok 2 number(s): "57 5"
Test #9:
score: 0
Accepted
time: 9ms
memory: 4356kb
input:
16 10 10 9 8 7 6 5 4 3 2 1
output:
57 3
result:
ok 2 number(s): "57 3"
Test #10:
score: 0
Accepted
time: 3ms
memory: 4400kb
input:
16 7 10 9 8 6 5 4 1
output:
49 1
result:
ok 2 number(s): "49 1"
Test #11:
score: 0
Accepted
time: 2ms
memory: 4016kb
input:
16 4 7 6 2 1
output:
52 9
result:
ok 2 number(s): "52 9"
Test #12:
score: 0
Accepted
time: 2ms
memory: 4124kb
input:
22 3 5 3 1
output:
100 1
result:
ok 2 number(s): "100 1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
22 1 1
output:
231 1
result:
ok 2 number(s): "231 1"
Test #14:
score: 0
Accepted
time: 55ms
memory: 9580kb
input:
22 4 10 8 3 1
output:
97 4
result:
ok 2 number(s): "97 4"
Test #15:
score: 0
Accepted
time: 57ms
memory: 9516kb
input:
22 5 10 7 6 3 1
output:
92 70
result:
ok 2 number(s): "92 70"
Test #16:
score: 0
Accepted
time: 69ms
memory: 9464kb
input:
22 6 10 9 8 7 3 1
output:
97 1
result:
ok 2 number(s): "97 1"
Test #17:
score: 0
Accepted
time: 98ms
memory: 9508kb
input:
22 10 10 9 8 7 6 5 4 3 2 1
output:
109 1
result:
ok 2 number(s): "109 1"
Test #18:
score: 0
Accepted
time: 2ms
memory: 4064kb
input:
14 2 10 1
output:
61 210
result:
ok 2 number(s): "61 210"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
18 2 2 1
output:
117 1
result:
ok 2 number(s): "117 1"
Test #20:
score: 0
Accepted
time: 246ms
memory: 32776kb
input:
30 2 9 1
output:
264 84
result:
ok 2 number(s): "264 84"
Test #21:
score: 0
Accepted
time: 191ms
memory: 28084kb
input:
29 2 9 1
output:
253 36
result:
ok 2 number(s): "253 36"
Test #22:
score: 0
Accepted
time: 22ms
memory: 7848kb
input:
25 2 8 1
output:
195 8
result:
ok 2 number(s): "195 8"
Test #23:
score: 0
Accepted
time: 756ms
memory: 63612kb
input:
30 4 10 9 5 1
output:
188 40
result:
ok 2 number(s): "188 40"
Test #24:
score: 0
Accepted
time: 1143ms
memory: 63692kb
input:
30 9 10 9 8 7 6 5 4 3 1
output:
184 6
result:
ok 2 number(s): "184 6"
Test #25:
score: 0
Accepted
time: 1041ms
memory: 63860kb
input:
30 8 10 9 8 7 4 3 2 1
output:
154 1
result:
ok 2 number(s): "154 1"
Test #26:
score: 0
Accepted
time: 1077ms
memory: 63860kb
input:
30 8 10 8 7 6 5 4 3 1
output:
155 1
result:
ok 2 number(s): "155 1"
Test #27:
score: 0
Accepted
time: 890ms
memory: 63548kb
input:
30 6 10 8 6 4 3 1
output:
150 4
result:
ok 2 number(s): "150 4"
Test #28:
score: 0
Accepted
time: 1230ms
memory: 63656kb
input:
30 10 10 9 8 7 6 5 4 3 2 1
output:
184 6
result:
ok 2 number(s): "184 6"
Test #29:
score: 0
Accepted
time: 650ms
memory: 53640kb
input:
29 6 10 9 7 5 3 1
output:
129 200
result:
ok 2 number(s): "129 200"
Extra Test:
score: 0
Extra Test Passed