QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760723 | #9568. Left Shifting 3 | Meowmeowmeow# | WA | 0ms | 15832kb | C++20 | 3.3kb | 2024-11-18 18:47:39 | 2024-11-18 18:47:39 |
Judging History
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'