QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351780 | #8225. 最小值之和 | JCY_ | 0 | 2ms | 5756kb | C++14 | 3.9kb | 2024-03-12 14:54:19 | 2024-03-12 14:54:19 |
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 - 1)], 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;
}
}
}
}
}
}
}
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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5756kb
input:
5 14 14 12 13 13
output:
No
result:
wrong answer Line 1 expected
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%