QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351809 | #8225. 最小值之和 | JCY_ | 11 | 2ms | 5864kb | C++14 | 4.0kb | 2024-03-12 15:17:13 | 2024-03-12 15:17:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
if (y < x) x = y;
}
int ceil_div(int x, int y) { return x <= 0 ? x / y : (x - 1) / y + 1; }
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
constexpr int MAXN = 82;
int n, a[MAXN], f[MAXN][MAXN][MAXN], temp[MAXN], ans[MAXN];
void print(int l, int r, int v) {
if (l == r) return;
int x, y = 0;
for (x = l; x < r; ++x) {
if (x == l && x + 1 == r) {
if (a[l] == a[r] && (a[l] - v) % (r - l) == 0) {
y = (a[l] - v) / (r - l);
break;
}
} else if (x == l) {
if (f[l + 1][r][a[l] % (r - l - 1)] >= a[l] && (a[l] - v) % (r - l) == 0) {
y = (a[l] - v) / (r - l);
break;
}
} else if (x + 1 == r) {
if (f[l][r - 1][a[r] % (r - l - 1)] >= a[r] && (a[r] - v) % (r - l) == 0) {
y = (a[r] - v) / (r - l);
break;
}
} else {
int up = (x - l) / __gcd(x - l, r - x - 1) * (r - x - 1);
for (y = 0; y < up; ++y) {
if (f[l][x][(v + y * (r - l)) % (x - l)] >= v + y * (r - l) &&
f[x + 1][r][(v + y * (r - l)) % (r - x - 1)] >= v + y * (r - l)) {
break;
}
}
if (y != up) break;
}
}
assert(x != r);
print(l, x, v + y * (r - l));
print(x + 1, r, v + y * (r - l));
for (int i = l; i < r; ++i) ans[i] += y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
if (n == 1) {
cout << (a[1] ? "No" : "Yes\n") << "\n";
return 0;
}
memset(f, -1, sizeof(f));
for (int l = n; l >= 1; --l) {
for (int r = l + 1; r <= n; ++r) {
for (int x = l; x < r; ++x) {
if (x == l && x + 1 == r) {
if (a[l] == a[r]) chkmax(f[l][r][a[l] % (r - l)], a[l]);
} else if (x == l) {
if (f[l + 1][r][a[l] % (r - l - 1)] >= a[l])
chkmax(f[l][r][a[l] % (r - l)], a[l]);
} else if (x + 1 == r) {
if (f[l][r - 1][a[r] % (r - l - 1)] >= a[r])
chkmax(f[l][r][a[r] % (r - l)], a[r]);
} else {
fill(temp, temp + r - l, -1);
int sx, sy, d = exgcd(x - l, r - x - 1, sx, sy);
sy = -sy;
int coef = max(ceil_div(-sx, (r - x - 1) / d), ceil_div(-sy, (x - l) / d));
sx += (r - x - 1) / d * coef;
sy += (x - l) / d * coef;
for (int i = 0; i < x - l; ++i) {
if (f[l][x][i] == -1) continue;
for (int j = 0; j < r - x - 1; ++j) {
if (f[x + 1][r][j] == -1) continue;
int c = f[l][x][i] - f[x + 1][r][j];
if (c % d) continue;
ll fst = f[l][x][i] - (ll)c / d * sx * (x - l);
if (fst >= 0) chkmax(temp[fst % (r - l)], (int)fst);
}
}
d = (x - l) / d * (r - x - 1);
for (int s = 0, td = d % (r - l), up = __gcd(r - l, td); s < up; ++s) {
auto nxt = [&](int v) {
v -= td;
return v < 0 ? v + r - l : v;
};
for (int turn = 0; turn < 2; ++turn) {
for (int i = s, j = nxt(s);; i = j, j = nxt(j)) {
chkmax(temp[j], temp[i] - d);
if (j == s) break;
}
}
}
for (int i = 0; i < r - l; ++i) chkmax(f[l][r][i], temp[i]);
}
}
}
}
if (f[1][n][0] == -1) {
cout << "No\n";
return 0;
}
cout << "Yes\n";
print(1, n, 0);
for (int i = 1; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
return 0;
}
/*
g++ B.cpp -o B -std=c++14 -O2 -Wall -Wextra -Wshadow -g -fsanitize=address,undefined
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 1ms
memory: 5728kb
input:
5 14 14 12 13 13
output:
Yes 14 0 6 7
result:
ok The answer is correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 5800kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 1
result:
ok The answer is correct.
Test #3:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
5 11 11 10 5 5
output:
Yes 6 5 0 5
result:
ok The answer is correct.
Test #5:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
5 10 10 10 4 4
output:
Yes 5 5 0 4
result:
ok The answer is correct.
Test #6:
score: 0
Accepted
time: 2ms
memory: 5784kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 0
Accepted
time: 1ms
memory: 5724kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 0
Accepted
time: 1ms
memory: 5808kb
input:
5 10 10 8 5 5
output:
Yes 6 4 0 5
result:
ok The answer is correct.
Test #10:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
5 24 24 28 28 26
output:
Yes 6 6 9 7
result:
ok The answer is correct.
Test #11:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
5 5 5 22 31 31
output:
Yes 5 0 11 20
result:
ok The answer is correct.
Test #12:
score: 0
Accepted
time: 0ms
memory: 5828kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 0
Accepted
time: 1ms
memory: 5768kb
input:
5 16 16 4 12 12
output:
Yes 16 0 2 10
result:
ok The answer is correct.
Test #14:
score: 0
Accepted
time: 0ms
memory: 5816kb
input:
5 29 29 24 26 26
output:
Yes 29 0 12 14
result:
ok The answer is correct.
Test #15:
score: 0
Accepted
time: 0ms
memory: 5808kb
input:
5 0 33 33 32 32
output:
Yes 0 33 0 32
result:
ok The answer is correct.
Test #16:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 0ms
memory: 5836kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 0ms
memory: 5816kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 1ms
memory: 5792kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 0ms
memory: 5792kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 0ms
memory: 5792kb
input:
5 6 7 7 6 6
output:
Yes 3 4 0 6
result:
ok The answer is correct.
Test #23:
score: 0
Accepted
time: 0ms
memory: 5812kb
input:
5 25 25 24 20 20
output:
Yes 13 12 0 20
result:
ok The answer is correct.
Test #24:
score: 0
Accepted
time: 1ms
memory: 5724kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 1ms
memory: 5724kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 0ms
memory: 5728kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 2ms
memory: 5812kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 2ms
memory: 5768kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 0ms
memory: 5808kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 233
output:
No
result:
ok The answer is correct.
Subtask #2:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #35:
score: 15
Accepted
time: 0ms
memory: 5816kb
input:
8 16 16 8 8 9 9 6 6
output:
Yes 16 0 8 0 9 0 6
result:
ok The answer is correct.
Test #36:
score: 0
Accepted
time: 2ms
memory: 5784kb
input:
8 16 16 9 21 21 23 23 23
output:
Yes 16 0 3 15 1 10 10
result:
ok The answer is correct.
Test #37:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
8 10 10 15 15 15 10 10 5
output:
Yes 10 0 6 6 1 6 1
result:
ok The answer is correct.
Test #38:
score: 0
Accepted
time: 0ms
memory: 5840kb
input:
8 13 13 15 15 24 24 24 10
output:
Yes 13 0 7 2 9 9 2
result:
ok The answer is correct.
Test #39:
score: 0
Accepted
time: 1ms
memory: 5808kb
input:
8 5 13 16 25 25 24 4 4
output:
Yes 1 3 4 9 8 0 4
result:
ok The answer is correct.
Test #40:
score: 0
Accepted
time: 1ms
memory: 5864kb
input:
8 1313 1695 1695 1129 1129 711 557 557
output:
Yes 654 1036 1 771 353 1 551
result:
ok The answer is correct.
Test #41:
score: -15
Runtime Error
input:
8 1386 1416 1416 1069 1069 390 645 645
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #77:
score: 0
Runtime Error
input:
49 28 28 28 24 37 37 33 36 36 29 43 43 41 41 29 48 51 51 44 49 50 50 9 9 15 18 18 3 17 17 9 13 17 17 13 13 0 6 6 16 21 25 25 19 7 19 19 17 4
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%