QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749949 | #9574. Strips | 523555337 | WA | 50ms | 4644kb | C++14 | 2.4kb | 2024-11-15 11:37:29 | 2024-11-15 11:37:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define se second
#define fi first
#define ret(i,a,b) for(int i = (a);i<=(b);++i)
const int N=2e5+5;
const int M=1e6+5;
const ll inf=1e18;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,m,k,w,x,ff;
int ans;
vector<int> noww;
vector<int> anss;
void work(int l,int r)
{
int tot=0,now=0;
if(ff==0) return ;
//printf("l=%d,r=%d\n",l,r);
if(r-l-1<k&&(!noww.empty()))
{
ff=0;
//printf("plf?");
return ;
}
int aa[N];
for(auto u:noww)
{
if(now==0)
{
now=u;
tot=1;
aa[tot]=now;
}
if(u>now+k-1)
{
now=u;
tot++;
aa[tot]=now;
}
//printf("u=%d,now=%d\n",u,now);
}
if(tot*k>r-l-1)
{
ff=0;
return ;
}
//cout<<"?!?\n";
//ret(i,1,tot) cout<<aa[i]<<" ";
//cout<<endl;
for(int i=tot;i;--i)
{
if(i==tot)
{
if(aa[i]+k-1<r)
{
break;
}
else
{
aa[i]=r-k;
}
}
else
{
if(aa[i]<=aa[i+1]-k) break;
else
{
aa[i]=aa[i+1]-k;
}
}
}
//printf("??");
if(aa[1]<=l)
{
ff=0;
//printf("aaplf?\n");
return ;
}
ret(i,1,tot) anss.pb(aa[i]);
ans+=tot;
return ;
}
void solve()
{
cin>>n>>m>>k>>w;
map<int,int> M;
ans=0;
ff=1;
anss.clear();
ret(i,1,n)
{
cin>>x;
M[x]=1;
}
ret(i,1,m)
{
cin>>x;
M[x]=2;
}
int now=0;
noww.clear();
for(auto u:M)
{
//printf("?u.fi=%d,u.se=%d\n",u.fi,u.se);
if(ff==0) break;
if(u.se==2)
{
//printf("?:now=%d,u.fi=%d,u.se=%d\n",now,u.fi,u.se);
work(now,u.fi);
noww.clear();
now=u.fi;
}
if(u.se==1) noww.pb(u.fi);
}
work(now,w+1);
if(ff) cout<<ans<<endl;
else cout<<"-1\n";
if(ff)
{
for(auto u:anss) cout<<u<<" ";
cout<<endl;
}
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4644kb
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
Wrong Answer
time: 50ms
memory: 4404kb
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:
-1 -1 -1 -1 -1 6 1 8 12 31 41 47 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 81 4 2 11 16 23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 35 43 87 92 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 8 24 28 41 65 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 11 26 48 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 1)