QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#383372	#7678. The Game	Giga_Cronos^#	TL	0ms	3820kb	C++23	3.2kb	2024-04-09 11:34:23	2024-04-09 11:34:23

Judging History

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

[2024-04-09 11:34:23]
评测

测评结果：TL
用时：0ms
内存：3820kb

查看

[2024-04-09 11:34:23]
提交

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 x = n - m - sum;
		// cout << x << "\n";
		multiset<int> ma;
		for (int i = 0; i < n; i++)
			ma.insert(a[i]);
		vector<int> ans;
		while (sum >= 0 && ma.size() - sum > m) {
			int mv = *ma.begin();
			ans.push_back(mv);
			int cnt = ma.count(mv);
			if (ma.size() - cnt + 1 <= m) {
				if (mv == b[0]) {
					ok = 0;
					break;
				}
				sum--;
			}
			ma.erase(ma.begin());
			ma.erase(ma.begin());
			ma.insert(mv + 1);
		}

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

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

		vector<int> ord;
		auto ita = ma.begin();
		for (int i = 0; i < ma.size(); i++) {
			a[i + n - ma.size()] = *ita;
			ita++;
		}
		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.count(j)) {
				ok = 0;
			} else {
				ans.push_back(j);
				ma.erase(ma.find(j));
				ma.erase(ma.begin());
				ma.insert(j + 1);
			}
		}

		ita = ma.begin();
		for (int i = 0; i < m; i++) {
			ok = (ok & (*ita == b[i]));
			ita++;
		}

		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;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3820kb

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:

result:

ok ok (6 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

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