QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#383393 | #7678. The Game | Giga_Cronos# | WA | 3ms | 3808kb | C++23 | 3.6kb | 2024-04-09 12:22:32 | 2024-04-09 12:22:32 |
Judging History
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)