QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1106 | #697914 | #9527. A Brand New Geometric Problem | ucup-team2818 | propane | Success! | 2024-11-02 20:09:33 | 2024-11-04 16:55:46 |
Details
Extra Test:
Time Limit Exceeded
input:
100000 10000 9340531200 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 ...
output:
result:
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#697914 | #9527. A Brand New Geometric Problem | propane | TL | 16ms | 5028kb | C++20 | 3.8kb | 2024-11-01 16:22:51 | 2024-11-06 13:24:00 |
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
using LL = long long;
int cnt;
int c[10005];
int id1[100005], id2[100005];
int get(LL x){
if (x <= 100000) return id1[x];
else return id2[10'000'000'000 / x];
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n; LL S, M;
cin >> n >> S >> M;
vector<LL> factor;
for(LL i = 1; i * i <= M; i++){
if (M % i == 0){
factor.push_back(i);
if (i * i != M){
factor.push_back(M / i);
}
}
}
sort(factor.begin(), factor.end(), greater<>());
factor.pop_back();
reverse(factor.begin(), factor.end());
while(!factor.empty() and factor.back() > S) factor.pop_back();
reverse(factor.begin(), factor.end());
for(int i = 0; i < factor.size(); i++){
LL x = factor[i];
if (x <= 100000) id1[x] = i;
else id2[10'000'000'000 / x] = i;
}
int cnt1 = 0;
for(int i = 0; i < n; i++){
LL x;
cin >> x;
if (M % x != 0) continue;
if (x == 1) cnt1 += 1;
else c[get(x)] += 1;
}
if (cnt1 > S){
LL keep = 0;
LL t = M, ss = 0, tot = 0;
for(LL i = 2; i * i <= t; i++){
if (t % i == 0){
int v = 0;
while(t % i == 0){
ss += i;
t /= i;
v += 1;
}
if (i <= S){
if (i != 2){
keep += min(v, c[get(i)]);
tot += v;
}
else{
int cnt2 = c[get(2)];
int cnt4 = (v >= 2 ? c[get(4)] : 0);
if (cnt2 >= v){
tot += v;
keep += v;
}
else{
int t = cnt2 + min(cnt4, (v - cnt2) / 2);
keep += t;
tot += t;
int remain = v - t;
tot += (remain + 1) / 2;
}
}
}
}
}
if (t > 1){
ss += t;
tot += 1;
if (t <= S) keep += min(1, c[get(S)]);
}
if (ss > S){
cout << -1 << '\n';
return 0;
}
tot -= keep;
keep += S - ss;
cout << n - keep + tot << '\n';
return 0;
}
const LL INF = 1e18;
LL ans = INF;
auto dfs = [&](auto &&dfs, int u, LL val, LL sum, int num){
if (S - sum - M / val - 35 > ans) return;
if (val == M){
ans = min(ans, abs(S - sum - cnt1) + num);
return;
}
if (u == factor.size()) return;
vector<LL> p1{val}, p2{sum};
{
while(1){
if (M / p1.back() % factor[u] == 0 and p2.back() + factor[u] <= S){
p1.push_back(p1.back() * factor[u]);
p2.push_back(p2.back() + factor[u]);
}
else break;
}
}
for(int i = p1.size() - 1; i >= 0; i--){
if (i <= c[u]) dfs(dfs, u + 1, p1[i], p2[i], num - i);
else dfs(dfs, u + 1, p1[i], p2[i], num - c[u] + (i - c[u]));
}
};
dfs(dfs, 0, 1, 0, n - cnt1);
if (ans > INF / 2) cout << -1 << '\n';
else cout << ans << '\n';
}