QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749949#9574. Strips523555337WA 50ms4644kbC++142.4kb2024-11-15 11:37:292024-11-15 11:37:29

Judging History

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

  • [2024-11-15 11:37:29]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:4644kb
  • [2024-11-15 11:37:29]
  • 提交

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)