QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383393#7678. The GameGiga_Cronos#WA 3ms3808kbC++233.6kb2024-04-09 12:22:322024-04-09 12:22:32

Judging History

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

  • [2024-04-09 12:22:32]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3808kb
  • [2024-04-09 12:22:32]
  • 提交

answer

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops",
// "omit-frame-pointer", "inline") #pragma GCC
// target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
// #pragma GCC option("arch=native", "no-zero-upper") // Enable AVX

/// UH Top
#include <bits/stdc++.h>
#define db(x)   cerr << #x << ':' << (x) << '\n';
#define all(v)  (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
// #define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t int128;
typedef pair<ll, ll> pii;
typedef pair<ld, ll> pdi;
typedef pair<ld, ld> pdd;
typedef pair<ld, pdd> pdp;
typedef pair<string, ll> psi;
typedef pair<ll, string> pls;
typedef pair<string, string> pss;
typedef pair<ll, pii> pip;
typedef pair<pii, pii> ppp;
typedef complex<ld> point;
typedef vector<point> polygon;
typedef vector<ll> vi;
typedef pair<point, int> ppi;
#define prec(n)                                                                \
	cout.precision(n);                                                         \
	cout << fixed
const ll mod = (1e9 + 7);
const ld eps = (1e-9);
const ll oo = (ll)(1e18 + 5);
#define pi   acos(-1)
#define MAXN (ll)(1e6 + 5)

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		vector<int> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];
		vector<int> b(m);
		for (int i = 0; i < m; i++)
			cin >> b[i];

		sort(all(a));
		sort(all(b));

		int cant = n - m;
		ll sum = 0;
		bool ok = 1;
		for (int i = 0; i < m; i++) {
			if (a[i + n - m] > b[i])
				ok = 0;
			else
				sum += (b[i] - a[i + n - m]);
		}

		if (sum > n - m || !ok) {
			cout << -1 << "\n";
			continue;
		}

		int rem = n;
		map<int, int> ma;
		for (int i = 0; i < n; i++)
			ma[a[i]]++;
		vector<int> ans;
		while (rem - sum > m) {
			int mv = ma.begin()->first;
			int cnt = ma[mv];
			// cout << mv << ' ' << sum << "\n";
			if (rem - cnt + 1 <= m) {
				if (b[m - (rem - cnt + 1)] < mv + 1) {
					ok = 0;
					break;
				}
				sum--;
			}
			ans.push_back(mv);
			ma[mv]--;
			while (!ma.empty() && ma.begin()->second == 0)
				ma.erase(ma.begin());
			ma[ma.begin()->second--];
			while (!ma.empty() && ma.begin()->second == 0)
				ma.erase(ma.begin());
			ma[mv + 1]++;
			rem--;
		}

		if (!ok) {
			cout << "-1\n";
			continue;
		}

		// for(auto x : ma)
		// 	cout << x << " ";
		// cout << "\n";

		// cout << rem << "\n";
		vector<int> ord;
		int cont = 0;
		for (auto y : ma) {
			for (int j = 0; j < y.second; j++) {
				a[cont + n - rem] = y.first;
				cont++;
			}
		}
		for (int i = 0; i < m; i++) {
			if (a[i + n - m] > b[i])
				ok = 0;
			for (int j = a[i + n - m]; j < b[i]; j++) {
				ord.push_back(j);
			}
		}

		if (!ok) {
			cout << "-1\n";
			continue;
		}

		sort(all(ord));

		for (auto j : ord) {
			if (!ma[j]) {
				ok = 0;
			} else {
				ans.push_back(j);
				ma[j]--;
				while (!ma.empty() && ma.begin()->second == 0)
					ma.erase(ma.begin());
				ma[ma.begin()->first]--;
				while (!ma.empty() && ma.begin()->second == 0)
					ma.erase(ma.begin());
				ma[j + 1]++;
			}
		}

		cont = 0;
		for (auto y : ma) {
			for (int j = 0; j < y.second; j++) {
				ok = (ok & b[cont] == y.first);
				cont++;
			}
		}

		if (!ok) {
			cout << "-1\n";
			continue;
		}

		cout << ans.size() << "\n";
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << " \n"[i + 1 == ans.size()];
	}

	return 0;
}

详细

Test #1:

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

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: 3ms
memory: 3808kb

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

result:

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