QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#851707	#9574. Strips	BUET_ALUCHASHI^#	WA	25ms	3876kb	C++17	2.8kb	2025-01-10 22:48:38	2025-01-10 22:49:42

Judging History

This is the latest submission verdict.

[2025-01-10 22:49:42]
Judged

Verdict: WA
Time: 25ms
Memory: 3876kb

Show

[2025-01-10 22:48:38]
Submitted

answer

#include <bits/stdc++.h>
#define lli long long
#define plli pair<lli, lli>
#define MAX 1e6 + 6
const int MOD = 1000000007;

using namespace std;
//segment tree updates precisely doesn,t add
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t=1;
    cin>>t;

    while(t--){

        int n,m,k,w;
        cin>>n>>m>>k>>w;

        vector<int> red(n);
        vector<int> black(m);

        for(int i=0;i<n;i++){
            cin>>red[i];
        }
        for(int i=0;i<m;i++){
            cin>>black[i];
        }
        black.push_back(MOD);
        sort(red.begin(),red.end());
        sort(black.begin(),black.end());
        m+=1;
        int indr=0;
        int left=0;
        vector<int> ans;
        bool tr=true;
        for(int i=0;i<m;i++){

            vector<int> curreds;
            while(indr<n && red[indr]<black[i]){
                curreds.push_back(red[indr]);
                indr++;
            }
            int right=black[i]-1;

            if(curreds.size()==0){
                left=black[i];
                continue;

            }
            
            int redind=0;
            vector<int> tmp;
            // cout<<left<<" "<<right<<" lrlr\n";
            while(redind<curreds.size()){
                int fir=curreds[redind];
                int last=fir+k-1;
                // cout<<fir<<" "<<last<<"\n";
                tmp.push_back(curreds[redind]);
                
                if(last>right){
                    int extra=last-right;
                    for(int tmpind=tmp.size()-1;tmpind>=0;tmpind--){
                        tmp[tmpind]-=extra;
                        extra=(tmpind>0?tmp[tmpind-1]+k:left+1)-tmp[tmpind];
                        // cout<<tmp[tmpind]<<" "<<extra<<" xxxxxxx\n";
                        if(extra<=0){
                            break;
                        }
                    }
                    if(extra>0){
                        tr=false;
                    }
                    break;

                }
                while(redind<curreds.size() && curreds[redind]<=last){
                    redind++;
                }
                
            }
            if(!tr){
                break;
            }
            // for(int tmpind=0;tmpind<tmp.size();tmpind++){
            //     cout<<tmp[tmpind]<<" ";
            // }cout<<" last "<<tmp.size()<<"\n";

            for(int tmpind=0;tmpind<tmp.size();tmpind++){
                ans.push_back(tmp[tmpind]);
            }

            left=black[i];

        }
        if(!tr){
            cout<<"-1\n";
        }else{
            cout<<ans.size()<<"\n";
            for(int i=0;i<ans.size();i++){
                cout<<ans[i]<<" ";
            }cout<<"\n";
        }


    }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3876kb

input:

4
5 2 3 16
7 11 2 9 14
13 5
3 2 4 11
6 10 2
1 11
2 1 2 6
1 5
3
2 1 2 6
1 5
2

output:

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100

Wrong Answer

time: 25ms

memory: 3876kb

input:

11000
3 8 2 53
32 3 33
35 19 38 20 1 30 10 6
7 10 1 42
3 14 4 36 28 40 22
17 20 12 41 27 7 1 19 13 9
6 6 13 78
55 76 53 32 54 58
62 45 21 4 7 61
8 7 3 68
9 26 54 31 22 3 38 65
34 16 58 47 52 29 53
5 8 4 33
33 5 30 6 15
27 12 9 28 19 2 13 10
6 1 2 48
8 12 48 1 41 31
40
7 6 7 61
20 19 30 52 49 17 40
3...

output:

2
3 32 
7
3 4 14 22 28 36 40 
3
32 48 76 
8
3 9 22 26 31 38 54 65 
3
5 15 30 
6
1 8 12 31 41 48 
4
17 30 39 49 
2
52 67 
1
27 
1
22 
1
62 
5
24 33 43 48 60 
2
4 31 
3
11 20 31 
3
3 16 33 
3
25 30 42 
3
3 17 60 
4
1 11 21 33 
2
54 66 
3
50 59 65 
3
50 62 78 
1
85 
4
2 11 16 23 
5
3 7 17 36 49 
2
1 45...

result:

wrong answer Integer parameter [name=l_i] equals to 76, violates the range [1, 66] (test case 3)