QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#626068 | #9422. Two-star Contest | ConsW | WA | 37ms | 4816kb | C++20 | 5.2kb | 2024-10-09 22:56:05 | 2024-10-09 22:56:05 |
Judging History
answer
#include<bits/stdc++.h>
#define i64 long long
#define u64 unsigned long long
#define ll long long
using namespace std;
typedef pair<i64, i64> pii;
const i64 MOD = 1e9 + 7;
const u64 P = 131;
inline i64 lowbit(i64 x) { return x & (-x); }
inline i64 highbit(i64 x) {
i64 cnt = 0;
do {
if (x == 1) return 1LL << cnt;
else ++cnt;
} while (x >>= 1);
}
inline i64 factory(i64 start, i64 end) {
if (start > end) return 0;
i64 cnt = 1;
while (start <= end) {
cnt *= start++;
cnt %= MOD;
}
return cnt;
}//阶乘(含模运算),从start乘到end
inline i64 gcd(i64 a, i64 b) {
while (b ^= a ^= b ^= a %= b);
return a;
}//最小公约数
inline bool isPrime(i64 x) {
for (int i = 2; i <= sqrt(x); ++i) {
if (x % i == 0) return false;
}
if (x != 1) return true;
else return false;
}
inline bool cmp(pii a, pii b) {
return a.first > b.first;
}
inline i64 query(i64 a, i64 b) {
i64 tmp;
cout << "? " << a << " " << b << endl;
cin >> tmp;
return tmp;
}
inline i64 to_i64(string s) {
stringstream ss(s);
i64 tmp;
ss >> tmp;
return tmp;
}//字符串转long long
inline i64 LIS(i64 arr[], i64 n) {
i64 dp[n], len = 0;
dp[0] = arr[0];
for (int i = 1; i < n; ++i) {
if (arr[i] > dp[len]) dp[++len] = arr[i];
else *(lower_bound(dp, dp + len, arr[i])) = arr[i];
}
return len + 1;
}
inline i64 qpow(i64 a, i64 n) {
i64 res = 1;
while (n) {
if (n & 1) res *= a;
a *= a;
a %= MOD;
n >>= 1;
res %= MOD;
}
return res;
}
struct st {
i64 s, sum = 0, pos;
vector<i64> p;
};
void solve() {
i64 n, m, k;
cin >> n >> m >> k;
st arr[n];
for (int i = 0; i < n; ++i) {
cin >> arr[i].s;
arr[i].pos = i;
for (int j = 0; j < m; ++j) {
i64 p;
cin >> p;
arr[i].p.emplace_back(p);
if (p != -1) arr[i].sum += p;
}
}
sort(arr, arr + n, [](st &a, st &b) { return a.s > b.s; });
i64 maxs = LLONG_MAX / 2, premaxs = maxs;
for (int i = 0; i < n; ++i) {
i64 tot = 0;
for (auto &item: arr[i].p) {
if (item == -1) tot += k;
}
if (maxs == 0) {
cout << "No" << endl;
return;
}
if (i > 0 && arr[i].s == arr[i - 1].s) {
i64 tmp;
if (arr[i].sum + tot >= premaxs) {
if (arr[i].sum < premaxs) {
i64 diff = premaxs - arr[i].sum - 1;
for (int j = 0; j < m; ++j) {
if (arr[i].p[j] == -1) {
if (diff < k) {
arr[i].p[j] = diff;
for (int l = j + 1; l < m; ++l) {
if (arr[i].p[l] == -1) arr[i].p[l] = 0;
}
break;
} else {
arr[i].p[j] = k;
diff -= k;
}
}
}
tmp = --premaxs;
} else {
// cout << "No" << endl;
// return;
}
} else {
for (int j = 0; j < m; ++j) {
if (arr[i].p[j] == -1) arr[i].p[j] = k;
}
tmp = arr[i].sum + tot;
}
if (tmp < maxs) maxs = tmp;
continue;
}
if (arr[i].sum + tot >= maxs) {
if (arr[i].sum < maxs) {
i64 diff = maxs - arr[i].sum - 1;
for (int j = 0; j < m; ++j) {
if (arr[i].p[j] == -1) {
if (diff < k) {
arr[i].p[j] = diff;
for (int l = j + 1; l < m; ++l) {
if (arr[i].p[l] == -1) arr[i].p[l] = 0;
}
break;
} else {
arr[i].p[j] = k;
diff -= k;
}
}
}
premaxs = maxs;
maxs--;
} else {
cout << "No" << endl;
return;
}
} else {
for (int j = 0; j < m; ++j) {
if (arr[i].p[j] == -1) arr[i].p[j] = k;
}
premaxs = maxs;
maxs = arr[i].sum + tot;
}
}
sort(arr, arr + n, [](st &a, st &b) { return a.pos < b.pos; });
cout << "Yes" << endl;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << arr[i].p[j] << " ";
}
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
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: 3568kb
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 5 2 5 0 5 3 5 1 4 No Yes 1 2 3 4 5 6 No Yes 10000 10000 10000 10000 10000 9999
result:
ok ok 5 cases (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 4816kb
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 96295 849 96295 96295 33907 7926 9461 70117 96295 96295 56792 96295 96295 96295 19527 96295 12828 30553 40825 67577 91517 77952 55631 63781 29385 96295 96295 96295 750 96295 96295 96295 Yes 72716304 72716304 66436933 72716304 45419040 55642613 72716304 62712753 72716304 2...
result:
wrong answer Participant cannot satisfy the constraint. (test case 37)