QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #772915 | #9574. Strips | buling | TL | 1ms | 5612kb | C++14 | 4.4kb | 2024-11-22 22:55:25 | 2024-11-22 22:55:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define lll i << 1
#define rrr i << 1 | 1
//
#define ll long long
#define int long long
#define ld long double
// #define rint register int
// #define inv inline void
// #define ini inline int
// inline int read()
// {
// int sum=0;
// char ch=getchar();
// while(ch>'9'||ch<'0') ch=getchar();
// while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar();
// return sum;
// }//读入优化
//
//
// inline void print(int x){
// if(!x){
// putchar('0');
// return;
// }
// int num[22],siz=0,px=x;
// while(px){
// siz++;
// num[siz]=px%10;
// px/=10;
// }
// while(siz){
// putchar(num[siz]+'0');
// siz--;
// }
// } //快速输出
long long max(long long a,long long b)
{
return a>b?a:b;
}
long long min(long long a,long long b)
{
return a<b?a:b;
}
const int N=2e5+6;
const int N2=1004;
int mod=998244353;
//int Mod=1e15+7;
const int INF=2e17;
const double eps=1e-10;
const double PI=3.1415926535;
//priority_queue<int , vector<int >, greater<int >> q;
//priority_queue<int > q;
//map<string ,int>mp,mmp;
//typedef pair<int ,int > PII;
//stack < PII > p;
//queue<int > q;
//char s1[2020],s2[2020];
//vector<vector<int>> c(n+13,vector<int>(m+3));
//map<int,int>mp;
//priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q[1001][1001],p;
//a.erase(unique(a.begin(), a.end()), a.end());
//char p,q;
//char s[N];
//deque<int > q;
//queue<int> q;
//using ull = unsigned long long;
//ull mod=212370440130137957ll;
//int f[N][N],a[N][N],b[N][N],c[N][N],dp[N][N],q[N],v[N][N];
//
//struct node
//{
//
// int x,y;
//
//}p[N];
//
//inline bool cmp(node w,node v)
//{
// if(w.x==v.x)
// return w.y<v.y;
//
// return w.x<v.x;
//}
//
//int fx[5]={-1,0,0,1};
//int fy[5]={0,-1,1,0};
//int q[N],q2[N];
int ma,mi;
int n,m,a[N],b[N],dd[N];
int ans=0;
void solve()
{
string s,s2;
int res=0,q,re;
ans=0;
cin>>n>>m>>re>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int j=1;j<=m;j++)
cin>>b[j];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
b[++m]=q+1;
int j=1;
for(int i=0;i<=m;i++)
{
for(;j<=n;)
{
deque<pair<int,int>> mp;
int k=j,l=b[i],tt=0;
if(b[i]<a[j]&&b[i+1]>a[j])
{
for(k=j;k<=n;k++)
{
if(b[i]<a[k]&&b[i+1]>a[k])
{
if(l>=a[k])
continue;
tt++;
int r=min(b[i+1]-1,a[k]+re-1);
int yy=r-re+1;
int mm=l-yy+1;
if(yy>l)
{
//mp[tt]+=yy-l-1;
if(yy-l-1!=0)
{
mp.push_back({tt,yy-l-1});
}
//mp.erase(tt);
}
else
{
while(mp.size())
{
auto[x,y]=mp.back();
if(y<=mm)
{
if(x==1)
{
cout<<-1<<"\n";
return ;
}
mm-=y;
mp.pop_back();
}
else
{
y-=mm;
mp.pop_back();
mp.push_back({tt,yy});
mm=0;
}
}
}
if(mm>0)
{
cout<<-1<<"\n";
return ;
}
l=r;
}
else
break;
}
int rer=b[i];
map<int,int> mp2;
while(mp.size())
{
auto[x,y]=mp.front();
mp.pop_front();
mp2[x]=y;
}
for(int qw=ans+1;qw<=ans+tt;qw++)
{
dd[qw]=rer+mp2[qw-ans]+1;
//cout<<qw<<" "<<j<<" "<<b[i]<<" "<<mp[qw-ans]<<" "<<rer<<" "<<dd[qw]<<"\n";
rer=dd[qw]+re-1;
}
j=k;
}
else
break;
ans+=tt;
}
}
cout<<ans<<"\n";
for(int i=1;i<=ans;i++)
cout<<dd[i]<<" ";
cout<<"\n";
}
signed main()
{
std::ios::sync_with_stdio(false);//取消cin与stdin同步,加速读入
cin.tie(0);cout.tie(0);
int t;
t=1;
cin>>t;
//pair<int,int > p[10];
while(t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5612kb
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
Time Limit Exceeded
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...