QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#245650	#7678. The Game	UNos_maricones	WA	6ms	3524kb	C++20	2.3kb	2023-11-10 08:54:13	2023-11-10 08:54:13

Judging History

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

[2023-11-10 08:54:13]
评测

测评结果：WA
用时：6ms
内存：3524kb

查看

[2023-11-10 08:54:13]
提交

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, lcf = 0;
    for (int cf = fa; cf <= fb; ++cf) {
      if (cput + sum < n - m) lcf = 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)lcf > 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;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3524kb

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:

result:

ok ok (6 test cases)

Test #2:

score: 0

Accepted

time: 0ms

memory: 3420kb

input:

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:

ok ok (7056 test cases)

Test #3:

score: 0

Accepted

time: 3ms

memory: 3412kb

input:

output:

-1
-1
2
1 2 
-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
2
2 3 
-1
-1
-1
2
1 1 
2
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
2
3 4 
-1
-1
-1
2
1 1 
2
1 3 
-1
-1
-1
2
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok ok (5880 test cases)

Test #4:

score: 0

Accepted

time: 2ms

memory: 3404kb

input:

output:

result:

ok ok (2640 test cases)

Test #5:

score: 0

Accepted

time: 6ms

memory: 3420kb

input:

output:

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

result:

ok ok (14112 test cases)

Test #6:

score: -100

Wrong Answer

time: 3ms

memory: 3472kb

input:

output:

-1
-1
-1
3
1 2 3 
-1
-1
-1
3
1 1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
2 3 4 
-1
-1
3
1 1 2 
3
1 2 3 
-1
-1
3
1 2 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
3 4 5 
-1
-1
3
1 1 3 
3
1 3 4 
-1
3
1 1 2 
3
1 2 3 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
1 1 4 
3
1 4 5 
...

result:

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