QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#695308#9422. Two-star ContestCharlie983WA 31ms5220kbC++142.7kb2024-10-31 19:44:322024-10-31 19:44:33

Judging History

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

  • [2024-10-31 19:44:33]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:5220kb
  • [2024-10-31 19:44:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
const int N = 1e6 + 10,M=210;
const int inf=0x3f3f3f3f,mod=998244353;
bool cmp(pair<int,vector<int>>x,pair<int,vector<int>>y)
{
    return x.first<y.first;
}
bool cmp1(pair<int,int>x,pair<int,int>y)
{
    return x.first<y.first;
}
void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    vector<pair<int,vector<int>>>a(n+1);
    vector<int>X;
    for(int i=1;i<=n;i++)
    {
        int rk;cin>>rk;
        X.push_back(rk);
        a[i].first=rk;
        vector<int>temp;
        for(int j=1;j<=m;j++)
        {
            int x;cin>>x;
            temp.push_back(x);
        }
        a[i].second=temp;
    }
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    vector<pair<int,int>>b(n+1);
    for(int i=1;i<=n;i++)
    {
        a[i].first=lower_bound(X.begin(),X.end(),a[i].first)-X.begin()+1;
        b[i].first=a[i].first;
        b[i].second=i;
    }
    sort(a.begin()+1,a.end(),cmp);
    sort(b.begin()+1,b.end(),cmp1);
    vector<pair<int,int>>s(n+1,{1e18,0});
    for(int i=1;i<=n;i++)
    {
        int sum=0,num=0;
        for(auto x:a[i].second)
        {
            if(x!=-1)sum+=x;
            else num++;
        }
        s[a[i].first].first=min(s[a[i].first].first,sum+num*k);
        s[a[i].first].second=max(a[i].first,sum);
        // cout<<s[i].first<<" "<<s[i].second<<endl;
    }

    int len=X.size();
    // for(int i=1;i<=len;i++)cout<<s[i].first<<" "<<s[i].second<<endl;
    for(int i=len-1;i>=1;i--)
    {
        // cout<<s[i].first<<" "<<s[i].second<<endl;
        if(s[i].second>s[i+1].first-1)
        {
            cout<<"No"<<endl;
            return;
        }
        s[i].first=min(s[i].first,s[i+1].first-1);
    }
    for(int i=1;i<=n;i++)
    {
        int sum=s[a[i].first].first;
        for(auto x:a[i].second)
        {
            if(x!=-1)sum-=x;
        }
        sum=max(0ll,sum);
        for(auto &x:a[i].second)
        {
            if(x!=-1)continue;
            if(sum>=k)
            {
                x=k;
                sum-=k;
            }
            else
            {
                x=sum;
                sum=0;
            }
        }
    }
    vector<pair<int,vector<int>>>ans(n+1);
    for(int i=1;i<=n;i++)
    {
        ans[b[i].second].second=a[b[i].first].second;
    }
    cout<<"Yes"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(auto x:ans[i].second)cout<<x<<" ";
        cout<<endl;
    }

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

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: 31ms
memory: 5220kb

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:

No
Yes
96295 849 96295 96295 33907 7926 9461 70117 
12828 30553 40825 67577 91517 77952 55631 63781 
96295 849 96295 96295 33907 7926 9461 70117 
96295 849 96295 96295 33907 7926 9461 70117 
Yes
72716304 58625957 66436933 0 45419040 55642613 
72716304 58625957 66436933 0 45419040 55642613 
Yes
97540...

result:

wrong answer Participant fails to find an answer while the jury found one. (test case 1)