QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643630#9422. Two-star ContestrayWA 28ms4340kbC++202.3kb2024-10-15 22:28:262024-10-15 22:28:33

Judging History

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

  • [2024-10-15 22:28:33]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:4340kb
  • [2024-10-15 22:28:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << ": " << x << '\n';

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
	for (T& x : v) {
		is >> x;
	}
	return is;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
	for (int i = 0; i < (int)v.size(); i++) {
		os << v[i] << (i + 1 != v.size() ? " " : "");
	}
	return os;
}


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

	sort(all(a));
	int last = -1;
	int pos = n;
	int mn = a[0].first;
	for (int u = 0; u < n; u++) {
		auto [s, i] = a[u];
		if (s != mn) {
			pos = u;
			break;
		}
		int sum = 0;
		for (int j = 0; j < m; j++) {
			if (p[i][j] == -1) p[i][j] = 0;
			sum += p[i][j];
		}
		last = max(last, sum);
	}

	// debug(last);
	// debug(pos);

	int cur = last;
	int last_s = 0;
	if (pos >= 0 && pos < n) {
		last_s = a[pos].first;
	}
	for (int u = pos; u < n; u++) {
		auto [s, i] = a[u];
		if (s != last_s) {
			last = cur;
			last_s = s;
			cur = last + 1;
		}
		int sum = 0, cnt = 0;
 		for (int j = 0; j < m; j++) {
			sum += (p[i][j] == -1 ? 0 : p[i][j]);
			cnt += (p[i][j] == -1);
		}
		if (sum > last) {
			cur = max(cur, sum);
			for (int j = 0; j < m; j++) {
				if (p[i][j] == -1) p[i][j] = 0;
			}
		} else {
			cur = last + 1;
			int diff = last + 1 - sum;
			// debug(last);
			// debug(diff);
			if (cnt * k < diff) {
				cout << "No\n";
				return;
			}

			for (int j = 0; j < m; j++) {
				if (p[i][j] == -1) {
					int t = min(diff, k);
					p[i][j] = t;
					diff -= t;
				}
			}
		}
	}

	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() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	//std::cout << std::fixed << std::setprecision(10);

	int T = 1;
	std::cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3652kb

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: 28ms
memory: 4340kb

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
96295 96295 56792 96295 75461 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 2485603...

result:

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