QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#645453#9422. Two-star Contestcurtain_cppWA 27ms4188kbC++235.0kb2024-10-16 18:28:082024-10-16 18:28:09

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 18:28:09]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:4188kb
  • [2024-10-16 18:28:08]
  • 提交

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+add);
        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();
}

详细

Test #1:

score: 100
Accepted
time: 1ms
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: 27ms
memory: 4188kb

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)