QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244230#7678. The GameinvadedWA 0ms3688kbC++173.1kb2023-11-08 22:04:432023-11-08 22:04:44

Judging History

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

  • [2023-11-08 22:04:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3688kb
  • [2023-11-08 22:04:43]
  • 提交

answer

#include<bits/stdc++.h>
#ifndef xxx
#define dbg(...) ;
#endif
using namespace std;
template<class T> ostream &operator<<(ostream &o, const vector <T> &v) { bool f=false; for(T i:v) { f?o<<' ':o; o<<(i); f=true; } return o; }
template<class T> void sort(T &v) { std::sort(v.begin(), v.end()); }
template<class T, class C> void sort(T &v, C c) { std::sort(v.begin(), v.end(), c); }
template<class T> void reverse(T &v) { std::reverse(v.begin(), v.end()); }
template<class T> bool is_sorted(T &v) { return std::is_sorted(v.begin(), v.end()); }
template<class T> inline void _min(T &x, const T &y) { x>y?x=y:x; }
template<class T> inline void _max(T &x, const T &y) { x<y?x=y:x; }
istream &operator>>(istream &i, __int128_t &x) { x=0; short f=1; char c=0; while(!isdigit(c)) { if(c=='-')f=-1; c=i.get(); } while(isdigit(c))x=x*10+c-'0', c=i.get(); x*=f; return i; }
ostream &operator<<(ostream &o, __int128_t x) { if(x==0) { o<<0; return o; } bool f=false; string s; if(x<0)f=true, x=-x; while(x)s+=x%10+'0', x/=10; reverse(s); if(f)o<<'-'; o<<s; return o; }
mt19937 mt(time(0));
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
constexpr int maxn=3e5+5;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3fll;
constexpr double pi=acos(-1.0);
constexpr double eps=1e-9;
int a[maxn], b[maxn];
vector<int>getans(int n, int m)
{
	sort(a+1, a+1+n);
	sort(b+1, b+1+m);
	vector<int>ans;
	auto check=[&]()->bool
	{
		int k=n-m;
		ll sum=0;
		for(int j=m; j>=1; j--)
		{
			int i=j-m+n;
			if(b[j]<a[i])
			{
				return false;
			}
			sum+=b[j]-a[i];
			//dbg(i,j,b[j],a[i]);
		}
		if(sum>k)return false;
		int res=k-sum;
		multiset<int>A(a+1, a+1+n);
		//dbg(res,sum);
		for(int i=1; i<=res; i++)
		{
			int x=*A.begin();
			A.erase(A.begin());
			ans.push_back(x);
			A.insert(++x);
			A.erase(A.begin());
		}
		//dbg(A,ans);
		vector<int>vec(A.begin(), A.end());
		//dbg(vec);
		int nowSum=0;
		for(int j=m; j>=1; j--)
		{
			int i=(int)vec.size()-1-(m-j);
			int x=vec[i];
			int d=b[j]-x;
			//dbg(x,b[j]);
			nowSum+=d;
			//dbg(x,nowSum,sum);
			if(d<0)return false;
			while(x<b[j])
			{
				ans.push_back(x++);
			}
			vec[i]=x;
		}
		multiset<int>ansA(vec.begin()+nowSum, vec.end());
		multiset<int>B(b+1, b+1+m);
		while(ansA.size()>B.size())
		{
			int x=*ansA.begin();
			ansA.erase(ansA.begin());
			ans.push_back(x);
			ansA.insert(x);
			ansA.erase(ansA.begin());
		}
		//dbg(ansA,ans);
		return ansA==B;
	};
	if(!check())return vector<int>();
	return ans;
}
int main()//MARK: main
{
#ifndef xxx
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
	cout<<fixed<<setprecision(10);
	int t;
	cin>>t;
	while(t--)
	{
		int n, m;
		cin>>n>>m;
		for(int i=1; i<=n; i++)
			cin>>a[i];
		for(int i=1; i<=m; i++)
			cin>>b[i];
		auto ans=getans(n, m);
		if(ans.empty())
		{
			cout<<-1<<'\n';
		}
		else
		{
			cout<<ans.size()<<'\n';
			cout<<ans<<'\n';
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3688kb

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 2 3 2
2
1 1
3
1 1 2

result:

wrong answer Wrong answer, the final sequence does not equal to B (test case 6)