QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#277697#5137. TowerkoalaWA 1128ms69080kbC++142.1kb2023-12-06 21:35:512023-12-06 21:35:52

Judging History

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

  • [2023-12-06 21:35:52]
  • 评测
  • 测评结果:WA
  • 用时:1128ms
  • 内存:69080kb
  • [2023-12-06 21:35:51]
  • 提交

answer

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>
#include <bitset>
using namespace std;
const int N = 500 + 9;
typedef long long ll;
int read() {
  int x = 0, s = 1; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') s = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  return x * s; 
}

int n, m, a[N], pre[N];

void solve() {
  cin >> n >> m;
  vector<int> cho;
  for (int i = 1; i <= n; ++i)
    cin >> a[i];
  sort(a + 1, a + 1 + n);
  n -= m;
  for (int i = 1; i <= n; ++i) {
    pre[i] = pre[i - 1] + a[i];
    int x = a[i];
    while (x) {
      for (int j = -n * 30; j <= n * 30; ++j) {
        if (x + j >= 1)
          cho.push_back(a[i] + j);
      }
      x >>= 1;
    }
    for (int j = 0; j < 60; ++j)
      cho.push_back(i + j * n);
  }
  
  sort(cho.begin(), cho.end());
  cho.erase(unique(cho.begin(), cho.end()), cho.end());
  double t2 = log(2);
  int Ans = 1e9;
  int pos = 1;
  for (int x : cho) {
    int pos = lower_bound(a + 1, a + 1 + n, x) - a;
    while (pos <= n && x > a[pos])
      pos++;
    if (pos > n)
      break;
    if (pos * x - pre[pos] >= Ans)
      break;
    // vector<int> res;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
      if (a[i] <= x) {
        // res.push_back(x - a[i]);
        ans += x - a[i];
      } else {
        int t = log(1.0 * a[i] / x) / t2;
        int r = min(abs((a[i] >> t) - x) + t, abs((a[i] >> t + 1) - x) + t + 1);
        if (t)
          r = min(r, abs((a[i] >> t - 1) - x) + t - 1);
        // res.push_back(r);
        ans += r;
      }
    }
    // nth_element(res.begin(), res.begin() + n - m, res.end());
    
    // for (int i = 0; i < n - m; ++i)
    //   ans += res[i];
    Ans = min(1LL * Ans, ans);
    // cout << ans << ' ';
  }
  
  cout << Ans << '\n';
}

int T;
int main() {
  ios::sync_with_stdio(false);
  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: 3672kb

input:

3
2 0
2 6
5 0
1 2 3 4 5
5 3
1 2 3 4 5

output:

2
4
1

result:

ok 3 number(s): "2 4 1"

Test #2:

score: -100
Wrong Answer
time: 1128ms
memory: 69080kb

input:

10
272 118
11 14 49 94 71 62 46 45 74 22 15 36 7 37 27 35 96 85 75 78 76 64 23 59 17 35 71 28 96 82 5 66 2 48 57 31 88 10 61 73 79 23 19 52 39 76 48 98 5 39 48 51 90 90 60 27 47 24 24 56 48 27 39 21 38 18 20 9 62 83 47 15 51 22 73 74 7 80 64 60 86 74 59 7 84 38 99 31 42 60 52 41 63 88 59 90 77 40 68...

output:

468
8
469
121
619
644
1026
234
659
72

result:

wrong answer 1st numbers differ - expected: '454', found: '468'