QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405835#8225. 最小值之和chenk0 2ms9836kbC++143.1kb2024-05-06 14:30:142024-05-06 14:30:14

Judging History

你现在查看的是最新测评结果

  • [2024-05-06 14:30:14]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:9836kb
  • [2024-05-06 14:30:14]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define rep(i, s, t) for (int i = s; i <= t; ++i)
#define per(i, s, t) for (int i = t; i >= s; --i)

const int N = 85;

int n, a[N];
int f[N][N][N];
tuple<int, int, int, int, int> las[N][N][N];
int g[N][N], sx[N][N], sy[N][N];
int ans[N];

int exgcd(int a, int b, int& x, int& y) {
	if(b == 0) {
		x = 1, y = 0;
		return a;
	}
	int tx, ty;
	int g = exgcd(b, a%b, tx, ty);
	x = ty;
	y = tx - (a / b) * ty;
	return g;
}

inline void dfs(int l, int r, int i) {
	//cerr << l << " " << r << " " << i << "\n";
	if(l >= r) return;
	auto [k, a, b, x, y] = las[l][r][i];
	rep(j, l, k-1) ans[j] += x;
	rep(j, k+1, r-1) ans[j] += y;
	dfs(l, k, a);
	dfs(k+1, r, b);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cout << fixed << setprecision(15); 
	cerr << fixed << setprecision(15);

	cin >> n;
	rep(i, 1, n) cin >> a[i];

	if(n == 1) {
		cout << (a[1] ? "No" : "Yes") << "\n";
		return 0;
	}

	rep(i, 1, n) rep(j, 1, n) g[i][j] = exgcd(i, j, sx[i][j], sy[i][j]);
	memset(f, -1, sizeof f);
	rep(i, 1, n) f[i][i][0] = a[i];
	rep(len, 2, n) rep(i, 1, n) {
		int j = i + len - 1;
		if(j > n) break;
		rep(k, i, j-1) rep(a, 0, k-i) if(f[i][k][a] != -1) rep(b, 0, j-k-1) if(f[k+1][j][b] != -1) {
			//cerr << "[" << i << ", " << k << ", " << a << "](" << f[i][k][a] << ") + [" << k+1 << ", " << j << ", " << b << "](" << f[k+1][j][b] << ")\n";
			int lenA = k-i, lenB = j-k-1;
			int p = f[i][k][a], q = f[k+1][j][b];
			ll x = -1, y = -1;
			int g = ::g[lenA][lenB];
			if(lenA == 0 && lenB == 0) {
				if(p == q) {
					x = y = 0;
				} else {
					continue;
				}
			} else if(lenA == 0) {
				if(q >= p && (q - p) % lenB == 0) {
					x = 0, y = (q - p) / lenB;
				} else {
					continue;
				}
			} else if(lenB == 0) {
				if(p >= q && (p - q) % lenA == 0) {
					x = (p - q) / lenA, y = 0;
				} else {
					continue;
				}
			} else {
				if((p - q) % g) continue;
				x = sx[lenA][lenB];
				y = sy[lenA][lenB];
				x *= (p - q) / g;
				y *= -(p - q) / g;
				x %= lenB / g; if(x < 0) x += lenB / g;
				y = (q - p + x * lenA) / lenB;
				if(y < 0) {
					y %= lenA / g; if(y < 0) y += lenA / g;
					x = (p - q + y * lenB) / lenA;
					if(x < 0) continue;
				}
			}
			assert(p - x * lenA == q - y * lenB);
			int t = g ? lenA * lenB / g : 0;
			int dx = g ? lenB / g : 0;
			int dy = g ? lenA / g : 0;
			int val = p - x * lenA;
			if(val < 0) continue;
			int len = j - i;
			rep(p, 1, len) {
				if(val < 0) break;
				if(val > f[i][j][val % len]) {
					f[i][j][val % len] = val;
					las[i][j][val % len] = {k, a, b, x, y};
				}
				val -= t;
				x += dx;
				y += dy;
			}
		}
	}
	if(f[1][n][0] > 0) {
		cout << "Yes" << "\n";
		dfs(1, n, 0);
		rep(i, 1, n-1) ans[i] += f[1][n][0] / (n-1);
		rep(i, 1, n-1) cout << ans[i] << " \n"[i == n-1];
	} else {
		cout << "No" << "\n";
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 11
Accepted
time: 2ms
memory: 9748kb

input:

5
14 14 12 13 13

output:

Yes
5 3 3 4

result:

ok The answer is correct.

Test #2:

score: 11
Accepted
time: 0ms
memory: 9688kb

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1

result:

ok The answer is correct.

Test #3:

score: 11
Accepted
time: 1ms
memory: 6364kb

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4

result:

ok The answer is correct.

Test #4:

score: 11
Accepted
time: 1ms
memory: 6228kb

input:

5
11 11 10 5 5

output:

Yes
5 4 1 2

result:

ok The answer is correct.

Test #5:

score: 11
Accepted
time: 0ms
memory: 9836kb

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1

result:

ok The answer is correct.

Test #6:

score: 11
Accepted
time: 1ms
memory: 6736kb

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1

result:

ok The answer is correct.

Test #7:

score: 11
Accepted
time: 1ms
memory: 6324kb

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8

result:

ok The answer is correct.

Test #8:

score: 0
Wrong Answer
time: 1ms
memory: 6020kb

input:

5
2 2 6 11 11

output:

No

result:

wrong answer Line 1 expected , found  Ga

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%