QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749109#9422. Two-star ContestYuu#WA 29ms4332kbC++233.2kb2024-11-14 22:41:382024-11-14 22:41:38

Judging History

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

  • [2024-11-14 22:41:38]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:4332kb
  • [2024-11-14 22:41:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long

//  The 2024 ICPC Kunming Invitational Contest

void sol(){
    int n, m, k; 
    std::cin>>n>>m>>k;

    std::vector V(n + 1, std::vector<int>(m + 1));
    std::vector info(n + 1, std::array<int, 4>{0, 0, 0, 0});

    for(int i = 1; i <= n;i++){
        std::cin>>info[i][0];
        info[i][3] = i;
        for(int j = 1;j <= m;j++){
            std::cin>>V[i][j];
            if(V[i][j] == -1) {
                info[i][2] += 1;
            }else{
                info[i][1] += V[i][j];
            }
        }
    }

    std::sort(info.begin(), info.end());
    std::vector<int>vi(n + 1, -1);
    for(int i = 1;i <= n;i++){
        int j = i, cV = -1, Mn = 0;
        while(j <= n && info[j][0] == info[i][0]){
            Mn = std::max(Mn, info[i][1]);
            if(info[i][2] == 0){
                if(cV == -1){
                    cV = info[i][1];
                    if(cV <= vi[i - 1]) {
                        std::cout<<"No\n";
                        return ;
                    }
                }else{
                    if(cV != info[i][1]){
                        std::cout<<"No\n";
                        return ;
                    }
                }
            }
            j++;
        }

        Mn = std::max(Mn, vi[i - 1] + 1);
        //  确保cV > vi[i - 1]
        if(cV == -1){
            //  取Mn为s[i]的最小值.
            for(int u = i;u < j;u++){
                vi[u] = Mn;
                if(info[u][1] + info[u][2] * k < Mn){
                    std::cout<<"No\n";
                    return ;
                }
                int cur = info[u][1], ii = info[u][3];
                for(int v = 1;v <= m;v++){
                    if(V[ii][v] == -1){
                        if(Mn - cur >= k){
                            cur = cur + k;
                            V[ii][v] = k;
                        }else{
                            V[ii][v] = Mn - cur;
                            cur = Mn;
                        }
                    }
                }
            }
        }else{
            if(Mn > cV){
                std::cout<<"No\n";
                return ;
            }
            for(int u = i;u < j;u++){
                vi[u] = cV;
                if(info[u][1] + info[u][2] * k < cV){
                    std::cout<<"No\n";
                    return ;
                }
                int cur = info[u][1], ii = info[u][3];
                for(int v = 1;v <= m;v++){
                    if(V[ii][v] == -1){
                        if(cV - cur >= k){
                            V[ii][v] = k;
                            cur = cur + k;
                        }else{
                            V[ii][v] = cV - cur;
                            cur = cV;
                        }
                    }
                }
            }
        }
        i = j - 1;
    }

    std::cout<<"Yes\n";
    for(int i = 1;i<=n;i++){
        for(int j = 1;j <= m;j++){
            std::cout<<V[i][j]<<" \n"[j == m];
        }
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1; std::cin>>t;
    while(t--) sol();  
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3516kb

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: 29ms
memory: 4332kb

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
-92125 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
-14090347 0 66436933 0 45419040 55642613
0 62712753 0 21765515 56544945 12385026
Yes
975402536 975402536 975402536 975402536 975402536 248560376 ...

result:

wrong answer Integer parameter [name=q_{i, j}] equals to -92125, violates the range [0, 96295] (test case 2)