QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#262518 | #7678. The Game | jean | WA | 10ms | 16468kb | C++14 | 3.4kb | 2023-11-23 20:06:32 | 2023-11-23 20:06:34 |
Judging History
answer
#include"bits/stdc++.h"
#define mid (l + ((r - l) >> 1))
using namespace std;
const long long N = 1e6 + 10;
long long sum[N << 3], ls[N << 3], rs[N << 3], root, cnt, a[N << 3];
void push_up(long long i) {
sum[i] = sum[ls[i]] + sum[rs[i]];
a[i] = a[ls[i]] + a[rs[i]];
}
void add(long long &i, long long l, long long r, long long pos, long long vol) {
if(!i) i = ++cnt;
if(l == r) {
sum[i] += l * vol;
a[i] += vol;
return ;
}
else if(pos <= mid) add(ls[i], l, mid, pos, vol);
else add(rs[i], mid + 1, r, pos, vol);
push_up(i);
}
long long query1(long long i, long long l, long long r, long long vol) {
//cout << l << " " << r << " " << mid << " " << a[i] << " " << vol << "\n";
//cout << a[ls[i]] << " " << a[rs[i]] << "\n";
//cout << sum[ls[i]] << " " << sum[rs[i]] << "\n";
if(l == r) return vol * l;
else if(vol <= a[rs[i]]) return query1(rs[i], mid + 1, r, vol);
else return query1(ls[i], l, mid, vol - a[rs[i]]) + sum[rs[i]];
}
long long query2(long long i, long long l, long long r) {
if(l == r) return l;
else if(a[ls[i]]) return query2(ls[i], l, mid);
else return query2(rs[i], mid + 1, r);
}
long long query3(long long i, long long l, long long r, long long k) {
// cout << l << " " << r << " " << mid << " " << a[i] << " " << k << "\n";
// cout << a[ls[i]] << " " << a[rs[i]] << "\n";
// cout << sum[ls[i]] << " " << sum[rs[i]] << "\n";
if(l == r) return l;
else if(k <= a[ls[i]]) return query3(ls[i], l, mid, k);
else return query3(rs[i], mid + 1, r, k - a[ls[i]]);
}
long long b[N];
void solve() {
root = 0;
long long n, m;
cin >> n >> m;
vector<long long> ans;
for(long long i = 1; i <= n; i++) {
long long x;
cin >> x;
add(root, 1, 1e9 + 10, x, 1);
}
long long sum = 0;
for(long long i = 1; i <= m; i++) {
cin >> b[i];
sum += b[i];
if(query3(root, 1, 1e9 + 10, n - m + i) > b[i]) {
cout << -1 << "\n";
return ;
}
}
// if(sum - query1(root, 1, 1e9 + 10, m) > a[root] - m) {
// cout << "-1" << "\n";
// return ;
// }
long long kk = 0;
sort(b + 1, b + 1 + m);
while(kk < n - m && sum - query1(root, 1, 1e9 + 10, m) != a[root] - m) {
long long now = query2(root, 1, 1e9 + 10);
ans.push_back(now);
add(root, 1, 1e9 + 10, now, -1);
add(root, 1, 1e9 + 10, now + 1, 1);
add(root, 1, 1e9 + 10, query2(root, 1, 1e9 + 10), -1);
kk++;
}
//cout << kk << "\n";
for(long long i = m; i >= 1; i--) {
if(kk >= n - m) break;
//cout << "$$$$$" << a[root] - m + i << "\n";
long long ai = query3(root, 1, 1e9 + 10, a[root] - m + i);
//cout << i << " " << ai << " " << b[i] << "\n";
if(ai > b[i]) {
cout << -1 << "\n";
return ;
}
while(ai < b[i]) {
ans.push_back(ai);
add(root, 1, 1e9 + 10, ai, -1);
add(root, 1, 1e9 + 10, ai + 1, 1);
//cout << "###" << query2(root, 1, 1e9 + 10) << "\n";
add(root, 1, 1e9 + 10, query2(root, 1, 1e9 + 10), -1);
ai++;
kk++;
}
}
for(long long i = 1; i <= m; i++) {
//cout << query3(root, 1, 1e9 + 10, a[root] - m + i) << " " << b[i] << "\n";
if(query3(root, 1, 1e9 + 10, a[root] - m + i) != b[i]) {
cout << "-1" << "\n";
return ;
}
}
cout << n - m << "\n";
for(auto i : ans) cout << i << " ";
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
long long t;
cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9744kb
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: 10ms
memory: 16468kb
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 ...
result:
wrong answer Jury has answer but participant has not (test case 344)