QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277676 | #5137. Tower | zzuqy# | WA | 110ms | 13360kb | C++20 | 1.9kb | 2023-12-06 21:23:45 | 2023-12-06 21:23:46 |
Judging History
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;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i) {
pre[i] = pre[i - 1] + a[i];
cin >> a[i];
int x = a[i];
while (x) {
for (int j = -n; j <= n; ++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;
for (int x : cho) {
int pos = lower_bound(a + 1, a + 1 + n, x) - a;
if (pos >= n)
break;
if (pos * x - pre[pos] >= Ans)
break;
vector<int> res;
for (int i = 1; i <= n; ++i) {
if (a[i] <= x) {
res.push_back(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);
}
}
nth_element(res.begin(), res.begin() + n - m, res.end());
long long ans = 0;
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3904kb
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: 110ms
memory: 13360kb
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:
454 7 436 108 570 636 994 227 656 56
result:
wrong answer 2nd numbers differ - expected: '3', found: '7'