QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#638252 | #9422. Two-star Contest | Passer_by | WA | 32ms | 8452kb | C++17 | 4.3kb | 2024-10-13 15:22:38 | 2024-10-13 15:22:38 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pos string::npos
#define endl '\n'
#define inf 1e18
typedef unsigned long long ull;
const int mod = 998244353;
const int N = 6e5+20;
const int Maxn = 2e5+5;
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
int Inv[N],F[N];//组合数C2
int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b);}
int lcm(int a,int b){return (a/gcd(a,b)*b);}
int km(int a,int b,int mod)
{int ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
int km1(int a,int b,int mod)//指数取模,2^2^i,单求2^i要取模MOD-1
{int ans=1;mod--;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
int C(int a,int b,int p){if(b>a) return 0;int res=1;for(int i=b,j=a;i>=1;i--,j--){res=res*j%p;res=res*km(i,p-2,p)%p;}return res;}
int Lucas(int a,int b,int p){if(a<p&&b<p) return C(a,b,p);return C(a%p,b%p,p)*Lucas(a/p,b/p,p)%p;}
int C2(int a,int b,int p){return F[a]*Inv[a-b]%p*Inv[b]%p;}
void C2init(int n,int p){n--;F[0]=F[1]=1;for(int i=2;i<=n;i++)F[i]=F[i-1]*i%p;Inv[n]=km(F[n],p-2,p);for(int i=n-1;i>=0;i--)Inv[i]=Inv[i+1]*(i+1)%p;}
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
int n,k,m,c[N];
struct node{
int s,l,r,id;
}b[N];
bool cmp(node x,node y){
return x.s>y.s;
}
void solve()
{
// vector<vector<int,int>> x;
cin>>n>>m>>k;
//memset(b,0,sizeof b);
for(int i=0;i<=n+1;i++){
b[i].s=0,b[i].l=0,b[i].r=0,b[i].id=0;
}
vector<vector<int> > a(n+10,vector<int>(m+10,0));
for(int i=1;i<=n;i++){
int x;cin>>x;
int cnt=0,l=0;
b[i].s=x;
for(int j=1;j<=m;j++){
cin>>a[i][j];
x=a[i][j];
if(x==-1) cnt++;
else l+=x;
}
b[i].l=l,b[i].r=l+cnt*k,b[i].id=i;
}
bool ok=1;
int num=-1,len=-1,cnt=-1;
sort(b+1,b+n+1,cmp);
// for(int i=1;i<=n;i++) cout<<b[i].s<<" ";
for(int i=1;i<=n;i++){
//cout<<i<<" ";
int xx=i,l=b[i].l,r=b[i].r,cc=0;
// while(b[i].s==b[xx+1].s&&xx+1<=n) {
// xx++,cc++;
// //len=j+1;
// if(b[xx].l>r||b[xx].r<l||l>r) ok=0;
// l=max(l,b[xx].l);
// r=min(r,b[xx].r);
// }
// if(cc!=0){
// if(num==-1) num=r;
// else {
// num--;
// if(l>num) ok=0;
// else{
// if(r<num) num=r;
// }
// }
// if(num<0) ok=0;
// for(int j=i;j<=i+cc;j++){
// if(num>b[j].r||num<b[j].l) ok=0;
// int sum=num-b[j].l;
// for(int g=1;g<=m;g++){
// if(a[b[j].id][g]!=-1) continue;
// else {
// if(sum>=k) sum-=k,a[b[j].id][g]=k;
// else if(sum!=0&&sum<k) a[b[j].id][g]=sum,sum=0;
// else a[b[j].id][g]=0;
// }
// }
// }
// i+=cc;
// //continue;
// }
//else{
if(b[i].s==b[i-1].s){
num=b[i].r;
}
else{
if(num==-1) num=r;
else{
num--;
if(l>num) ok=0;
else{
if(r<num) num=r;
}
}}
if(num<0) ok=0;
int sum=num-b[i].l;
//cout<<num<<" ";
if(num>b[i].r||num<b[i].l) ok=0;
for(int g=1;g<=m;g++){
if(a[b[i].id][g]!=-1) continue;
else {
if(sum>=k) sum-=k,a[b[i].id][g]=k;
else if(sum!=0&&sum<k) a[b[i].id][g]=sum,sum=0;
else a[b[i].id][g]=0;
}
}
//}
}
if(ok==0) {
cout<<"No"<<endl;
return ;
}
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
signed main()
{
ios;
int T=1;
//C2init(N,mod);
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: 5672kb
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: 32ms
memory: 8452kb
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 5)