QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#543406 | #7678. The Game | AmiyaCast | WA | 1ms | 9992kb | C++14 | 2.5kb | 2024-09-01 16:40:07 | 2024-09-01 16:40:07 |
Judging History
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9700kb
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: 9992kb
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)