QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#368056#7678. The GameliswtWA 9ms3764kbC++201.5kb2024-03-26 19:22:302024-03-26 19:22:31

Judging History

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

  • [2024-03-26 19:22:31]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3764kb
  • [2024-03-26 19:22:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int T;
int n,m;
int a[N];
int b[N];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		for(int i=1;i<=m;i++)
		{
			cin>>b[i];
		}
		vector<int>ans;
		sort(a+1,a+n+1,cmp);
		sort(b+1,b+m+1,cmp);
		int add=0,del=0;
		multiset<int>u,v;
		for(int i=1;i<=m;i++)
		{
			add+=b[i]-a[i];
			u.insert(a[i]);
		}
		for(int i=m+1;i<=n;i++)
		{
			del++;
			v.insert(a[i]);
		}
//		int det=del-add;
		while(del>0&&del-add>0)
		{
//			cout<<del<<"----"<<add<<endl;
//			for(auto op:u)cout<<op<<" ";cout<<endl;
//			for(auto op:v)cout<<op<<" ";cout<<endl;
			auto x=v.begin();
			auto y=u.begin();
			v.erase(x);
			ans.push_back(*x);
			if(*x+1>*y)
			{
				u.erase(y);
				v.insert(*y);
				u.insert(*x+1);
				add--;
			}
			else
			{
				v.insert(*x+1);
			}
			v.erase(v.begin());
			del--;
		}
//		cout<<"ans is~~~~~~~~~~~~~~~~~~~"<<endl;
		if(add<del)
		{
			cout<<"-1"<<endl;
			continue;
		}
		int ok=1;
		for(int i=m;i>=1;i--)
		{
			auto x=u.begin();
			a[i]=*x;
			u.erase(x);
//			cout<<a[i]<<"~~~"<<endl;
			if(a[i]>b[i])
			{
				ok=0;
				break;
			}
			while(a[i]<b[i])
			{
				ans.push_back(a[i]);
				a[i]++;
			}
		}
		if(!ok)
		{
			cout<<"-1"<<endl;
			continue;
		}
		cout<<ans.size()<<endl;
		for(auto x:ans)
		{
			cout<<x<<" ";
		}
		cout<<endl;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

input:

6
5 3
1 2 2 3 3
2 3 4
4 2
1 2 2 4
2 4
5 2
2 3 3 4 4
5 5
6 1
1 1 1 1 1 1
4
4 2
1 1 1 2
2 2
4 1
1 1 1 1
2

output:

2
1 3 
-1
3
2 4 4 
5
1 1 1 2 3 
2
1 1 
-1

result:

ok ok (6 test cases)

Test #2:

score: -100
Wrong Answer
time: 9ms
memory: 3548kb

input:

7056
4 3
1 1 1 1
1 1 1
4 3
1 1 1 1
1 1 2
4 3
1 1 1 1
1 1 3
4 3
1 1 1 1
1 1 4
4 3
1 1 1 1
1 1 5
4 3
1 1 1 1
1 1 6
4 3
1 1 1 1
1 2 2
4 3
1 1 1 1
1 2 3
4 3
1 1 1 1
1 2 4
4 3
1 1 1 1
1 2 5
4 3
1 1 1 1
1 2 6
4 3
1 1 1 1
1 3 3
4 3
1 1 1 1
1 3 4
4 3
1 1 1 1
1 3 5
4 3
1 1 1 1
1 3 6
4 3
1 1 1 1
1 4 4
4 3
1 1...

output:

-1
1
1 
2
1 2 
3
1 2 3 
4
1 2 3 4 
5
1 2 3 4 5 
2
1 1 
3
1 1 2 
4
1 1 2 3 
5
1 1 2 3 4 
6
1 1 2 3 4 5 
4
1 2 1 2 
5
1 2 1 2 3 
6
1 2 1 2 3 4 
7
1 2 1 2 3 4 5 
6
1 2 3 1 2 3 
7
1 2 3 1 2 3 4 
8
1 2 3 1 2 3 4 5 
8
1 2 3 4 1 2 3 4 
9
1 2 3 4 1 2 3 4 5 
10
1 2 3 4 5 1 2 3 4 5 
3
1 1 1 
4
1 1 1 2 
5
1 1 ...

result:

wrong answer Wrong answer, number of operation is not correct (test case 3)