QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643681 | #9422. Two-star Contest | curtain_cpp# | WA | 23ms | 4416kb | C++23 | 4.9kb | 2024-10-15 23:05:32 | 2024-10-15 23:05:32 |
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.rbegin(),a.rend());
int cur=a[0].second.second;
vector<int>g(n);
g[0]=cur;
int mx=cur;
for(int i=1;i<n;i++){
if(a[i].first.first==a[i-1].first.first){
g[i]=min(mx,a[i].second.second);
cur=min(cur,g[i]);
}else{
auto [x,y]=a[i].second;
if(x>=cur){
cout<<"No"<<"\n";
return;
}
cur=min(cur-1,y);
g[i]=cur;
mx=cur;
}
}
for(int i=0;i<n;i++){
// debug(a[i].first.second);
}
for(int i=0;i<n;i++){
int idx=a[i].first.second;
int st=a[i].second.first;
//pdebug(st,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++){
for(int j=0;j<m;j++){
cout<<ans[i][j]<<" ";
}
cout<<'\n';
}
}
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: 0ms
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: 23ms
memory: 4416kb
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 58625957 66436933 0 45419040 55642613 72716304 62712753 72716304 21765515...
result:
wrong answer Participant cannot satisfy the constraint. (test case 14)