QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543453#7678. The GameAmiyaCastWA 0ms9948kbC++142.5kb2024-09-01 16:52:242024-09-01 16:52:24

Judging History

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

  • [2024-09-01 16:52:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9948kb
  • [2024-09-01 16:52:24]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define pii make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,b,a) for(int i=b;i>=a;--i)
const ll inf = 1145141919810;
using namespace std;
inline ll read() {
	ll x=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9') {
		if (c=='-')  f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void print(ll x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
	return ;
}
inline void pprint(ll x) {
	print(x);
	puts("");
}
const int N = 3e5 + 7;
ll a[N], b[N], c[N], d[N];
bool cmp(ll x, ll y) {
	return x > y;
}
int n, m, cnt;
int slv1() {
	rep(i, 1, n) c[i] = a[i];
	sort(c + 1, c + 1 + n);
	vector<int> q;
	for(int i = 1; i <= n - m;) {
		int j;
		for(j = i; j <= n; ++j) {
			if(c[j] == c[i]) continue;
			else {
				j--;
				break;
			}
		}
		if(j - i + 1 == 1) {
			i++;
			continue;
		} else {
			i = j;
			c[j]++;
		}
	}
	rep(i, 1, n - m)
	q.pb(c[i]);
	sort(c + 1, c + 1 + n, cmp);
	sort(b + 1, b + 1 + m, cmp);
	rep(i, 1, m) {
		if(c[i] != b[i])
			return -1;
	}
	pprint(q.size());
	for(auto x:q) {
		print(x);
		putchar(' ');
	}
	puts("");
	return 1;
}
int slv2() {
	sort(a + 1, a + 1 + n, cmp);
	sort(b + 1, b + 1 + m, cmp);
	vector<int> q, qq;
	ll rst = n - m, sum = 0;
	rep(i, 1, m){
		if(a[i] > b[i]){
			return -1;
		}
		if(b[i] - a[i] <= rst){
			rep(j, a[i], b[i] - 1){
				qq.pb(j);
			}
			rst -= b[i] - a[i];
            sum += b[i] - a[i];
		}else{
			return -1;
		}
	}

	priority_queue<ll> _q;
	for (int i = n; i > m; i--) {
        _q.push(-a[i]);
    }
	while(_q.size() > sum){
		ll x = -_q.top();
		if(x >= a[m]) {
			break;
		}
        q.push_back(x);
		_q.pop();
		x++;
		_q.push(-x);
		_q.pop();
	}

    for (auto i: qq) {
        q.push_back(i);
        _q.pop();
    }
    while(_q.size()){
		ll x = -_q.top();
		if(x >= b[m]) {
			return -1;
		}
        q.push_back(x);
		_q.pop();
		x++;
		_q.push(-x);
		_q.pop();
	}

	pprint(q.size());

	for(auto x:q){
		print(x); putchar(' ');
	}
	puts("");
	return 1;
}
void slv() {
	n = read(), m = read();
	rep(i, 1, n) a[i] = read();
	rep(i, 1, m) b[i] = read();
	if(n < m) {
		puts("-1");
		return ;
	}
	int ans2 = slv2();
	if(ans2 == 1) return;
	int ans1 = slv1();
	if(ans1 == 1) return;
	puts("-1");
	return ;
}
signed main() {
	int T = read();
	while(T--) {
		slv();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

result:

ok ok (6 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 9912kb

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

result:

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