QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245649#7678. The GameUNos_mariconesWA 1ms3496kbC++202.3kb2023-11-10 08:52:032023-11-10 08:52:04

Judging History

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

  • [2023-11-10 08:52:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3496kb
  • [2023-11-10 08:52:03]
  • 提交

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[i]; --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.begin());
        curr.insert(be + 1);
        curr.erase(curr.begin());
      }

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

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

    if (can) {
      cout << n - m << '\n';
      assert(ans.size() == n - m && curr.size() == 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: 3496kb

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

result:

wrong answer Jury has answer but participant has not (test case 3)