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
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
*/
详细
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:
4 14 10 7 2 -1 2 5 1 -1
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)