結果
問題 | No.3051 Make All Divisible |
ユーザー |
![]() |
提出日時 | 2025-03-07 23:56:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,866 bytes |
コンパイル時間 | 4,173 ms |
コンパイル使用メモリ | 287,536 KB |
実行使用メモリ | 8,608 KB |
最終ジャッジ日時 | 2025-03-07 23:56:35 |
合計ジャッジ時間 | 18,422 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 WA * 17 TLE * 2 |
ソースコード
#include <bits/stdc++.h>#include <bits/stdc++.h>#include <bits/stdc++.h>using namespace std;// #include <atcoder/modint>// using namespace atcoder;// using mint = modint998244353;using ll = long long;#define fix(x) fixed << setprecision(x)#define rep(i, n) for(int i = 0; i < n; ++i)#define all(x) (x).begin(),(x).end()template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}constexpr ll INFLL = (1LL << 62), MOD = 998244353;constexpr int INF = (1 << 30);int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int t;cin >> t;while(t--){int n,k;cin >> n >> k;vector<ll> a[2];int tot = 0;rep(i,n){ll x;cin >> x;a[x>=k].emplace_back(x%k);tot += x%k;}if(tot%k){cout << "-1\n";continue;}if(!tot){cout << "0\n";continue;}int l = -1, r = a[1].size()+1, ans = -1;sort(all(a[1]));while(l+1<r){int md = (l+r)/2, cnt = 0;priority_queue<int> pq;for(int x:a[0]) pq.emplace(x);rep(i,a[1].size()) pq.emplace(a[1][i]+k*(i<md));bool f = true;while(f && pq.top()>0){++cnt;vector<int> v;rep(i,k){if(!pq.top()){f = false;break;}v.emplace_back(pq.top()-1);pq.pop();}for(int x:v) pq.emplace(x);}if(f) r = md, ans = cnt;else l = md;}cout << ans << '\n';}return 0;}