QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760723#9568. Left Shifting 3Meowmeowmeow#WA 0ms15832kbC++203.3kb2024-11-18 18:47:392024-11-18 18:47:39

Judging History

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

  • [2024-11-18 18:47:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:15832kb
  • [2024-11-18 18:47:39]
  • 提交

answer

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

#define int long long
#define MAXN 500005

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};
        }
        for(int i = 1; i <= m; i ++) {
            cin >> b[i];
            mm ++;
            sc[mm] = {b[i],2};
            mm ++;
            sc[mm] = {b[i]+k,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 --;
            }
            if(p2 && c[i].t == 1 || c[i].x < k) {
                g[i] = 3;
                continue;
            }
            if(p2) g[i] = 2;
            if(c[i].t == 1) g[i] = 1;
            r[i] = x;
         //   cout<<g[i]<<" "<<r[i]<<" "<<x<<" "<<p1<<" "<<p2<<"\n";
            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";
        } 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;
}
/*
3
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
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 15832kb

input:

4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc

output:

0

0

0

0


result:

wrong answer 1st numbers differ - expected: '2', found: '0'