QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#772855#9574. StripsbulingRE 1ms5624kbC++144.0kb2024-11-22 22:25:172024-11-22 22:25:19

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 22:25:19]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5624kb
  • [2024-11-22 22:25:17]
  • 提交

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;)
		{
			map<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(mp[tt]==0)
								mp.erase(tt);
						}
						else
						{
							for (auto it = mp.rbegin(); it != mp.rend(); it++)
							{
							    auto[x,y]=*it;
							    if(y<=mm)
							    {
							    	if(x==1)
							    	{
							    		cout<<-1<<"\n";
										return ;
									}
							    	mm-=y;
							    	mp.erase(x);	
								}
								else
								{
									y-=mm;	
									mm=0;
								}
							}
						}
						if(mm>0)
						{
                            cout<<-1<<"\n";
							return ;
                        }
						l=r;
					}
					else
						break;
						
				}
				int rer=b[i];
				for(int qw=ans+1;qw<=ans+tt;qw++)
				{
					dd[qw]=rer+mp[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: 5624kb

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...

output:


result: