QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#760821	#9574. Strips	Meowmeowmeow^#	WA	87ms	15996kb	C++20	3.8kb	2024-11-18 19:26:19	2024-11-18 19:26:20

Judging History

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

[2024-11-18 19:26:20]
评测

测评结果：WA
用时：87ms
内存：15996kb

查看

[2024-11-18 19:26:19]
提交

answer

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

#define int long long
#define MAXN 1400005

int n,m,k,L,nn,mm;
int a[MAXN];
int b[MAXN];
struct aa {
    int x,t;
}c[MAXN],sc[MAXN];
int g[MAXN],f[MAXN],r[MAXN];

bool cmp(aa a,aa b) {
    return a.x < b.x;
}

signed main() {
    //ios::sync_with_stdio(0);
   //cin.tie(0);
    int T;
    cin >> T;
    while(T --) {
        for(int i = 0; i <= max(nn,mm)+3; i ++) {
            c[i] = {0,0};
            sc[i] = {0,0};
            g[i] = 0;
            f[i] = 0;
            r[i] = 0;
        }
        nn = 0; mm = 0;
        for(int i = 0; i <= max(n,m); i ++) {
            a[i] = 0; b[i] = 0;
        }
        cin >> n >> m >> k >> L;
        for(int i = 1; i <= n; i ++) {
            cin >> a[i];
            mm ++;
            sc[mm] = {a[i],1};
            mm ++;
            sc[mm] = {a[i]+k,0};
            mm ++;
            sc[mm] = {a[i]+k-1,0};
            
        }
        for(int i = 1; i <= m; i ++) {
            cin >> b[i];
            mm ++;
            sc[mm] = {b[i],2};
            mm ++;
            sc[mm] = {b[i]+k,0};
            if(b[i] != 1) {
                mm ++;
                sc[mm] = {b[i]-1,0};
            }
        }
        mm ++;
        sc[mm] = {L,0};
        mm ++;
        sc[mm] = {k,0};
        sort(sc+1,sc+mm+1,cmp);
        for(int i = 1; i <= mm; i ++) {
            if(sc[i].x > L) continue;
            if(sc[i].x == c[nn].x) {
                c[nn].t = max(c[nn].t,sc[i].t);
            } else {
                nn ++;
                c[nn] = sc[i]; 
            }
        }
        int p1 = 0,p2 = 0;
        int x = nn;
        bool fl = 0;
        for(int i = nn; i >= 1; i --) {
           // cout<<i<<" "<<c[i].x<<" "<<c[i].t<<"\n";
            while(x >= 1 && c[i].x-c[x].x < k) {
                if(c[x].t == 1) p1 ++;
                if(c[x].t == 2) p2 ++;
                x --;
            }
            r[i] = x;
//            cout<<g[i]<<" "<<r[i]<<" "<<x<<" "<<p1<<" "<<p2<<"\n";
            
           if((p2 || c[i].x < k) && c[i].t == 1 ) {
                g[i] = 3;
            if(c[i].t == 1) p1 --;
            if(c[i].t == 2) p2 --;
                continue;
            }
            if(c[i].x < k) {
                g[i] = 2;
            if(c[i].t == 1) p1 --;
            if(c[i].t == 2) p2 --;
                continue;
            }
            
            if(p2) g[i] = 2;
            if(c[i].t == 1) g[i] = 1;
            if(c[i].t == 1) p1 --;
            if(c[i].t == 2) p2 --;
        }
        for(int i = 1; i <= nn; i ++) {
            if(g[i] == 3) f[i] = 1e18;
            if(g[i] == 1) f[i] = f[r[i]]+1;
            if(g[i] == 2) f[i] = f[i-1];
            if(g[i] == 0) f[i] = min(f[r[i]]+1,f[i-1]);
           // cout<<T<<" "<<i<<":"<<f[i]<<" "<<r[i]<<" "<<g[i]<<"\n";
        }
        if(f[nn] > 1e17) {
            cout<<-1<<"\n";
            continue; 
        } else cout<<f[nn]<<"\n";
      //  continue;    
        x = nn;
        int cnt = 0;
        while(x > 0) {
          //  cnt ++;
            //if(cnt >= 100) break;
         // cout<<x<<" "<<r[x]<<" "<<g[x]<<" "<<f[x]<<"?\n";
        //    if(x == 2) break;
            if(g[x] == 1) 
            {
                cout<<c[x].x-k+1<<" ";
                x = r[x];
            }
            if(g[x] == 2) x --;
            if(g[x] == 0) {
                if(f[r[x]]+1 > f[x-1]) {
                    x --;
                } else {
                    cout<<c[x].x-k+1<<" ";
                    x = r[x];
                }
            }
            //cout<<i<<" "<<f[i]<<"\n";
        }
        cout<<"\n";
    
    }
    return 0;
}
/*
5
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
*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 15996kb

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: 87ms

memory: 15876kb

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

result:

wrong answer Participant didn't find a solution but the jury found one. (test case 18)