QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643781 | #9422. Two-star Contest | curtain_cpp# | WA | 30ms | 4200kb | C++23 | 4.9kb | 2024-10-16 00:13:50 | 2024-10-16 00:13:54 |
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());
int cur=a[0].second.first;
vector<int>g(n);
g[0]=cur;
int mx=-inf;
for(int i=1;i<n;i++){
if(a[i].first.first==a[i-1].first.first){
if(a[i].second.second<=mx+1 ){
cout<<"No"<<"\n";
return;
}
g[i]=max(mx+1,a[i].second.first);
cur=min(cur,g[i]);
}else{
auto [x,y]=a[i].second;
if(y<=cur){
cout<<"No"<<"\n";
return;
}
mx=cur;
cur=max(cur+1,x);
g[i]=cur;
}
}
for(int i=0;i<n;i++){
int idx=a[i].first.second;
int st=a[i].second.first;
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: 3620kb
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: 30ms
memory: 4200kb
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 0 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 ...
result:
wrong answer Participant cannot satisfy the constraint. (test case 2)