QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#865848 | #9574. Strips | lmz20050701 | WA | 26ms | 3712kb | C++17 | 3.4kb | 2025-01-22 00:46:57 | 2025-01-22 00:46:59 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define db double
#define P point
#define Fr(i,a,b) for(int i=a;i<=b;i++)
#define Fr_(i,a) for(auto i:a)
#define pb push_back
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fir first
#define sec second
#define pq priority_queue
#define mkp make_pair
#define memset(a,b) memset(a,b,sizeof(a))
#define new_opt friend bool operator
#define endl '\n'
#define ok cout<<"ok"<<endl
using namespace std;
const int N=2e6+10;
const int N_=1e3+10;
const int M=998244353;
const int inf=2e9;
int n,m,k,w;
vector<int> check(int l,int r,vector<int> v)
{
//cout<<"l and r : "<<l<<' '<<r<<endl;
//Fr_(i,v) cout<<i<<' ';cout<<endl;
vector<int> ans;
deque<pii> q;
Fr_(i,v)
{
//if(!q.empty()) cout<<"q.back(): "<<q.back().sec<<endl;
if(!q.empty()&&i<=q.back().sec) continue;
int it=lower_bound(v.begin(),v.end(),i+k-1)-v.begin();
while(v[it]>i+k-1) it--;
//cout<<"v[it]:"<<i<<' '<<v[it]<<endl;
if(q.empty())
{
int tmp=max(v[it],l+k-1);
q.pb({tmp-k+1,tmp});
}
else{
int len=k;
while(!q.empty()&&q.back().sec+len>=v[it])
{
pii tmp=q.back();
q.pop_back();
len+=tmp.sec-tmp.fir+1;
}
if(q.empty())
{
int tmp=max(l+len-1,v[it]);
q.pb({tmp-len+1,tmp});
}
else{
q.pb({v[it]-len+1,v[it]});
}
}
}
//cout<<l<<' '<<r<<endl;
//cout<<q.back().sec<<endl;
if(q.back().sec>r) return ans;
else
{
while(!q.empty())
{
pii tmp=q.front();
q.pop_front();
while(tmp.fir<=tmp.sec)
{
ans.pb(tmp.fir);
tmp.fir+=k;
}
}
//cout<<"ans: ";
//Fr_(i,ans) cout<<i<<' ';cout<<endl;
return ans;
}
}
/*
1
5 2 1 100
1 3 5 7 9
6 10
*/
void slv()
{
cin>>n>>m>>k>>w;
vector<pii> v;
Fr(i,1,n)
{
int x;
cin>>x;
v.pb({x,0});
}
Fr(i,1,m)
{
int x;
cin>>x;
v.pb({x,1});
}
sort(v.begin(),v.end());
v.pb({w+1,1});
/*if(k==1)
{
cout<<n<<endl;
Fr(i,0,n+m-1)
{
if(v[i].sec==0) cout<<v[i].fir<<' ';
}
cout<<endl;
return ;
}*/
int l=1;
vector<int> t;
vector<int> ans;
Fr_(i,v)
{
if(i.sec==0)
{
t.pb(i.fir);
}
else{
if(t.size()==0)
{
l=i.fir+1;
t.clear();
}
else{
vector<int> tmp=check(l,i.fir-1,t);
t.clear();
l=i.fir+1;
if(tmp.size()==0)
{
cout<<-1<<endl;
return ;
}
else{
Fr_(j,tmp) ans.pb(j);
}
}
}
}
cout<<ans.size()<<endl;
Fr_(i,ans) cout<<i<<' ';
cout<<endl;
}
signed main()
{
fastio;
int o=1;
cin>>o;
while(o--) slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
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 1 6 9 14 -1 2 1 4 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 26ms
memory: 3584kb
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 2 32 7 3 4 14 22 28 36 40 3 22 46 63 8 1 4 17 20 30 35 54 59 3 3 14 30 6 1 3 5 7 41 43 4 14 27 34 47 2 42 65 1 27 1 21 1 40 5 10 33 42 47 60 2 1 31 3 11 19 29 3 1 9 31 3 25 30 42 3 1 17 50 4 1 11 21 32 2 50 52 3 43 53 65 4 42 52 62 78 1 78 4 1 8 15 21 5 1 7 17 36 39 -1 2 7 ...
result:
wrong answer There is no stripe covering red cell 76 (test case 3)