QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #639596 | #5137. Tower | Lynia | WA | 59ms | 3924kb | C++23 | 3.5kb | 2024-10-13 20:43:06 | 2024-10-13 20:43:17 |
Judging History
answer
///////////
// // //
// ////////////////////
// // //
//
///////////
//
//
// // // //////// /\ /////////
// // // // // // //
// //////// // // // // //
// // // // // // //
////////// //////// // // // /////////////
#pragma GCC optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>
using namespace std;
#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define endl '\n'
#define px first
#define py second
#define DEBUG cout<<-1<<endl
using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
out << '(' << p.first << ", " << p.second << ')';
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
for (T i : ve)
out << i << ' ';
return out;
}
template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
for (auto i : mp)
out << i << '\n';
return out;
}
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };
//#include "Lynia.h"
const int mod = 998244353;
const int N = 5e3 + 10;
const ll _2[] = { 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296 };
struct node {
ll value, id, cnt;
bool operator<(const node& a)const {
return value < a.value;
}
};
void solve(int CASE)
{
int n, m; cin >> n >> m;
var a = vector<ll>(n + 1, 0);
fa(i, 1, n) cin >> a[i];
// 总数为 nlog(a[i])
multiset<node>se;
fa(i, 1, n) {
ll now = a[i];
ll cnt = 0;
while (now) {
se.insert({ now,i,cnt });
cnt++;
now /= 2;
}
}
// 枚举可能的中位数
ll ans = INF;
for (var& [now, id, cnt] : se) {
ll res = cnt;
var ve = vector<ll>();
fa(i, 1, n) {
if (i == id)continue;
if (a[i] <= now)res += now - a[i], ve.pb(now - a[i]);
else {
ll k = upper_bound(_2, _2 + 31, a[i] / now) - _2 - 1;
ll sheng = a[i] / _2[k];
res += k + sheng - now;
ve.pb(k + sheng - now);
}
}
sort(all(ve), greater<ll>());
fa(i, 0, m - 1) res -= ve[i];
ans = min(ans, res);
}
cout << ans << endl;
return;
}
int main()
{
//SetConsoleOutputCP(CP_UTF8);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _;
fa(i, 1, _)solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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: 59ms
memory: 3924kb
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:
485 3 483 116 617 663 1057 241 678 55
result:
wrong answer 1st numbers differ - expected: '454', found: '485'