QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#860577 | #9574. Strips | chenyiwei27 | RE | 12ms | 73720kb | C++17 | 2.3kb | 2025-01-18 14:05:04 | 2025-01-18 14:05:50 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
ll input(){
ll ans=0;
char c=getchar();
bool flag=0;
while(c<'0'||c>'9'){
if(c=='-')flag=1;
c=getchar();
}
while(c>='0'&&c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
if(flag)ans=-ans;
return ans;
}
void print(ll ans,char c=0,bool flag=1){
if(ans<0){
putchar('-');
ans=-ans;
}
if(ans>=10)print(ans/10,c,0);
putchar('0'+ans%10);
if(flag&&c!=0)putchar(c);
}
ll T,n,m,k,w;
ll r[maxn],b[maxn],ans[maxn],tot;
struct lll{
ll s,t;
queue<ll>p;
}l[maxn];
void init(){
tot=0;
for(ll i=0;i<=m+1;i++){
while(l[i].p.size())l[i].p.pop();
l[i].s=l[i].t=0;
}
}
bool operate(lll a){
//cout<<"period: "<<a.s<<" to "<<a.t<<endl<<"members: ";
//for(ll i=0;i<a.p.size();i++)print(a.p[i],' ');
//cout<<endl;
if(a.p.size()==0)return 1;
ll strip[n]={0},cnts=0;
/*for(ll i=0;i<a.p.size();i++){
if(i!=0&&strip[cnts]+k-1>=a.p[i])continue;
strip[++cnts]=a.p[i];
}*/
bool flag=0;
while(a.p.size()){
ll x=a.p.front();a.p.pop();
if(flag&&strip[cnts]+k-1>=x)continue;
flag=1;
strip[++cnts]=x;
}
for(ll i=cnts;i>=1;i--){
if(i==cnts){
if(strip[i]+k-1>a.t){
strip[i]=a.t-k+1;//strip[i]+k-1=a.t;
}
}
else{
if(strip[i]+k-1>=strip[i+1]){
strip[i]=strip[i+1]-k;//strip[i]+k-1=strip[i+1]-1
}
}
}
if(strip[1]<a.s)return 0;
for(ll i=1;i<=cnts;i++){
ans[++tot]=strip[i];
}
return 1;
}
int main(){
T=input();
while(T--){
n=input();m=input();
k=input();w=input();
init();
for(ll i=1;i<=n;i++)
r[i]=input();
sort(r+1,r+n+1);
for(ll i=1;i<=m;i++)
b[i]=input();
b[0]=0;
b[m+1]=w+1;
sort(b+1,b+m+1);
ll cnta=1,cntb=0,cnt=0;
while(1){
if(cnta>n){
if(b[cntb]<r[cnta-1])cntb++;
l[cnt].t=b[cntb]-1;
break;
}
if(r[cnta]<b[cntb]){
l[cnt].p.push(r[cnta]);
cnta++;
}
else{
l[cnt].t=b[cntb]-1;
l[++cnt].s=b[cntb]+1;
cntb++;
}
}
for(ll i=1;i<=cnt;i++){
if(!operate(l[i])){
print(-1,'\n');
goto END;
}
}
print(tot,'\n');
for(ll i=1;i<=tot;i++)print(ans[i],' ');
putchar('\n');
END:;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 73720kb
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 2 7 10 14 -1 2 1 5 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Runtime Error
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...