QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245624#7678. The GameUNos_maricones#WA 1ms3424kbC++202.3kb2023-11-10 06:59:082023-11-10 06:59:09

Judging History

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

  • [2023-11-10 06:59:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3424kb
  • [2023-11-10 06:59:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ff   first
#define ss   second
#define pb   push_back

typedef long long  ll;
typedef pair<ll,ll>  pii;

const ll N = 4e5 + 10;
const ll mod = 1e9 + 7;
const ll oo = 1e18;


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

  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL

  int t; cin >> t;
  while (t--) {

    int n,m; cin >> n >> m;
    vector <int> a(n), b(m);
    for (auto &e : a) cin >> e;
    for (auto &e : b) cin >> e;

    sort (a.begin(), a.end());
    sort (b.begin(), b.end());

    int can = 1;
    if (m > n) can = 0;
    if (can == 0) {
      cout << -1 << '\n';
      continue;
    }

    ll sum = 0, fa = a[n - m], fb = b[0];
    vector <int> ty2;

    for (int i = n - 1, j = m - 1; j >= 0; --i, --j) {
      if (a[i] > b[j]) can = 0;
      else {
        if (sum + b[j] - a[i] > n - m) {
          can = 0;
          break;
        }
        for (int k = b[j] - 1; k >= a[j]; --k) ty2.pb(k);
        sum += b[j] - a[i];
      }
    }
    reverse(ty2.begin(), ty2.end());

    if (can == 0) {
      cout << -1 << '\n';
      continue;
    }

    vector <int> ans;
    multiset <int> curr;
    for (auto &e : a) curr.insert(e);

    int cput = 0, idx = 0;
    for (int cf = fa; cf <= fb; ++cf) {
      while (cput + sum < n - m) {
        int be = *curr.begin();
        if (be == cf) break;
        ans.pb(be);
        cput++;
        curr.erase(curr.lower_bound(be));
        curr.insert(be + 1);
        be = *curr.begin();
        curr.erase(curr.lower_bound(be));
      }

      if (cf < fb) {
        curr.erase(curr.lower_bound(ty2[idx]));
        curr.insert(ty2[idx] + 1);
        int be = *curr.begin();
        curr.erase(curr.lower_bound(be));
        ans.pb(ty2[idx++]);
      }
    }
    while (idx < sum) {
      curr.erase(curr.lower_bound(ty2[idx]));
      curr.insert(ty2[idx] + 1);
      int be = *curr.begin();
      curr.erase(curr.lower_bound(be));
      ans.pb(ty2[idx++]);
    }

    if (curr.size() > m) can = 0;

    if (can) {
      cout << n - m << '\n';
      assert(ans.size() == n - m);
      for (auto &e : ans) cout << e << ' ';
      cout << '\n';
    }
    else cout << -1 << '\n';

  }

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3424kb

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 1 
-1
3
2 2 3 
5
1 1 1 2 3 
2
1 1 
-1

result:

wrong answer Wrong answer, erase a number that does not exist (test case 1)