QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645438 | #9422. Two-star Contest | curtain_cpp | WA | 31ms | 4244kb | C++23 | 5.0kb | 2024-10-16 18:22:52 | 2024-10-16 18:22:53 |
Judging History
answer
//Not all efforts result in success, but giving up is sure to result in failure.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <numeric>
#include <bitset>
#include <functional>
#include <iomanip>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL,LL> PII;
//typedef tuple<LL,LL,LL> tup;
#define make_pair() mk
#define int long long
const int N = 1e5+10;
const double pi = acos(-1);
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3fLL;
#define debug(x) cout<<"[debug]"#x<<"="<<x<<'\n';
#define pdebug(a,b) cout<<(#a)<<':'<<a<<' '<<(#b)<<':'<<b<<'\n'
#define tdebug(a,b,c) cout<<(#a)<<':'<<a<<' '<<(#b)<<':'<<b<<' '<<(#c)<<':'<<c<<'\n'
#define videbug(a) cout<<(#a)<<':';for(int i=0;i<a.size();i++)cout<<' '<<a[i];cout<<'\n';
// Make bold hypotheses and verify carefully
// - You REALLY need some key observations...
// - Don't trust seemaxgly trival conclusions
// - Do something instead of nothing and stay organized
// - Don't get stuck on one approach
// - Formalization is the death of intuition
template <int T>
struct ModInt {
const static int MD = T;
int x;
ModInt(LL x = 0)
: x(x % MD) {}
int get() { return x; }
ModInt operator+(const ModInt& that) const {
int x0 = x + that.x;
return ModInt(x0 < MD ? x0 : x0 - MD);
}
ModInt operator-(const ModInt& that) const {
int x0 = x - that.x;
return ModInt(x0 < MD ? x0 + MD : x0);
}
ModInt operator*(const ModInt& that) const {
return ModInt((long long)x * that.x % MD);
}
ModInt operator/(const ModInt& that) const {
return *this * that.inverse();
}
void operator+=(const ModInt& that) {
x += that.x;
if (x >= MD)
x -= MD;
}
void operator-=(const ModInt& that) {
x -= that.x;
if (x < 0)
x += MD;
}
void operator*=(const ModInt& that) { x = (long long)x * that.x % MD; }
void operator/=(const ModInt& that) { *this = *this / that; }
ModInt inverse() const {
int a = x, b = MD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
if (u < 0)
u += MD;
return u;
}
friend ostream& operator<<(ostream& os, ModInt x) {
os << x.get();
return os;
}
};
const int mod=998244353;
typedef ModInt<mod> mint;
const LL mod1=2147483648;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
inline __int128 read() {
__int128 x = 0, f = 1; char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
inline void write(__int128 x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
void solve()
{
int n,m,k;cin>>n>>m>>k;
vector<pair<PII,PII>>a(n);
vector<vector<int>>ans(n,vector<int>(m));
for(int i=0;i<n;i++){
int s;cin>>s;
int sum=0,cnt=0;
for(int j=0;j<m;j++){
int t;cin>>t;
ans[i][j]=t;
if(t==-1) {cnt++;continue;}
sum+=t;
}
a[i]={{s,i},{sum,sum+cnt*k}};
}
sort(a.begin(),a.end(),[&](pair<PII,PII> x,pair<PII,PII> y){
if(x.first.second==y.first.second){
return x.second>y.second;
}
return x<y;
});
vector<int>g(n);
int last = -1, cur = -1;
for(int i=0;i<n;i++){
int add = max(0ll, last + 1 - a[i].second.first);
if(add > a[i].second.second) {
cout << "No\n";
return ;
}
a[i].second.first+=add;
g[i]=a[i].second.first+add;
cur = max(cur, a[i].second.first);
if(i + 1 < n && a[i + 1].first.first != a[i].first.first){
last = cur;
}
}
for(int i=0;i<n;i++){
int idx=a[i].first.second;
int st=a[i].second.first;
//pdebug(idx,g[i]);
for(int j=0;j<m;j++){
if(ans[idx][j]==-1){
if(st+k<=g[i]){
st+=k;
ans[idx][j]=k;
}else{
if(g[i]<=st) {
ans[idx][j]=0;
}else ans[idx][j]=g[i]-st,st=g[i];
}
}
}
}
cout<<"Yes"<<"\n";
for(int i=0;i<n;i++){
int sum=0;
for(int j=0;j<m;j++){
cout<<ans[i][j]<<" ";
sum+=ans[i][j];
}
cout<<'\n';
//debug(sum)
}
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
int t;t=1;
cin>>t;
while(t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
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: 31ms
memory: 4244kb
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 97540253...
result:
wrong answer Participant cannot satisfy the constraint. (test case 14)