QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #408068 | #8285. Shell Sort | light_ink_dots# | AC ✓ | 1578ms | 63608kb | C++14 | 2.0kb | 2024-05-09 17:26:44 | 2024-05-09 17:26:46 |
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: 1ms
memory: 4008kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
8 4 6 3 2 1
output:
15 4
result:
ok 2 number(s): "15 4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4016kb
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: 3784kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
8 1 1
output:
28 1
result:
ok 2 number(s): "28 1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 0
Accepted
time: 8ms
memory: 4288kb
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: 4332kb
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: 7ms
memory: 4308kb
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: 4224kb
input:
16 4 7 6 2 1
output:
52 9
result:
ok 2 number(s): "52 9"
Test #12:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
22 3 5 3 1
output:
100 1
result:
ok 2 number(s): "100 1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
22 1 1
output:
231 1
result:
ok 2 number(s): "231 1"
Test #14:
score: 0
Accepted
time: 57ms
memory: 9600kb
input:
22 4 10 8 3 1
output:
97 4
result:
ok 2 number(s): "97 4"
Test #15:
score: 0
Accepted
time: 60ms
memory: 9496kb
input:
22 5 10 7 6 3 1
output:
92 70
result:
ok 2 number(s): "92 70"
Test #16:
score: 0
Accepted
time: 62ms
memory: 9336kb
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: 87ms
memory: 9372kb
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: 4012kb
input:
14 2 10 1
output:
61 210
result:
ok 2 number(s): "61 210"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
18 2 2 1
output:
117 1
result:
ok 2 number(s): "117 1"
Test #20:
score: 0
Accepted
time: 274ms
memory: 32772kb
input:
30 2 9 1
output:
264 84
result:
ok 2 number(s): "264 84"
Test #21:
score: 0
Accepted
time: 232ms
memory: 27900kb
input:
29 2 9 1
output:
253 36
result:
ok 2 number(s): "253 36"
Test #22:
score: 0
Accepted
time: 25ms
memory: 7736kb
input:
25 2 8 1
output:
195 8
result:
ok 2 number(s): "195 8"
Test #23:
score: 0
Accepted
time: 1022ms
memory: 63600kb
input:
30 4 10 9 5 1
output:
188 40
result:
ok 2 number(s): "188 40"
Test #24:
score: 0
Accepted
time: 1468ms
memory: 63560kb
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: 1374ms
memory: 63564kb
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: 1281ms
memory: 63608kb
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: 1223ms
memory: 63560kb
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: 1578ms
memory: 63596kb
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: 916ms
memory: 53480kb
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