QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#660937#9422. Two-star ContestEunoiayWA 20ms4212kbC++201.7kb2024-10-20 13:59:442024-10-20 13:59:46

Judging History

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

  • [2024-10-20 13:59:46]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:4212kb
  • [2024-10-20 13:59:44]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;
using i64 = long long;

void solve() {
	int n, m, k;
	cin >> n >> m >> k;

	vector<int> s(n);
	vector p(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		for (int j = 0; j < m; j++) {
			cin >> p[i][j];
		}
	}

	vector<i64> l(n), r(n);
	for (int i = 0; i < n; i++) {
		int x = 0;
		for (int j = 0; j < m; j++) {
			if (p[i][j] != -1) {
				l[i] += p[i][j];
			} else {
				x += 1;
			}
		}
		r[i] = l[i] + 1LL * x * k;
	}

	vector<int> o(n);
	iota(o.begin(), o.end(), 0);
	sort(o.begin(), o.end(), [&](int i, int j) {
		if (s[i] != s[j]) {
			return s[i] < s[j];
		}
		return r[i] < r[j];
	});

	auto setToZero = [&](int i) {
		for (int j = 0; j < m; j++) {
			if (p[i][j] == -1) {
				p[i][j] = 0;
			}
		}
	};

	i64 lst = l[o[0]];
	int i = 0;
	for ( ; i < n && s[o[i]] == s[o[0]]; i++) {
		setToZero(o[i]);
	}

	i64 mxv = lst;
	int prev = i - 1;
	for (; i < n; i++) {
		if (s[o[i]] != s[o[prev + 1]]) {
			lst = mxv;
			prev = i - 1;
		}
		int t = o[i];
		if (r[t] <= lst) {
			cout << "No\n";
			return;
		}
		if (l[t] > lst) {
			mxv = max(l[t], mxv);
			setToZero(t);
		} else {
			i64 need = lst - l[t] + 1;
			for (int j = 0; j < m; j++) {
				if (p[t][j] == -1) {
					i64 val = min(need, k);
					need -= val;
					p[t][j] = val;
				}
			}
			mxv = max(mxv, lst + 1);
		}
	}

	cout << "Yes\n";
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << p[i][j] << " \n"[j == m - 1];
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3852kb

input:

5
3 4 5
5 1 3 -1 -1
2 -1 5 -1 5
3 3 -1 -1 4
2 3 10
10000 5 0 -1
1 10 10 10
2 3 10
10 1 2 3
100 4 5 6
2 3 10
100 1 2 3
10 4 5 6
2 3 10000
100 -1 -1 -1
1 -1 -1 -1

output:

Yes
1 3 5 3
0 5 0 5
3 4 0 4
No
Yes
1 2 3
4 5 6
No
Yes
1 0 0
0 0 0

result:

ok ok 5 cases (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 20ms
memory: 4212kb

input:

1013
3 2 1
1 -1 -1
2 0 1
3 -1 -1
4 8 96295
302790137 -1 849 -1 -1 33907 7926 9461 70117
695984050 -1 -1 56792 -1 -1 -1 19527 -1
302790137 12828 30553 40825 67577 91517 77952 55631 63781
302790137 29385 -1 -1 -1 750 -1 -1 -1
2 6 72716304
892657961 -1 -1 66436933 -1 45419040 55642613
892657961 -1 6271...

output:

Yes
0 0
0 1
1 1
Yes
0 849 0 0 33907 7926 9461 70117
45942 0 56792 0 0 0 19527 0
12828 30553 40825 67577 91517 77952 55631 63781
29385 0 0 0 750 0 0 0
Yes
0 0 66436933 0 45419040 55642613
0 62712753 0 21765515 56544945 12385026
Yes
975402536 975402536 975402536 975402536 975402536 248560376 0 0 0
975...

result:

wrong answer Participant cannot satisfy the constraint. (test case 2)