QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#582134 | #9167. Coprime Array | ucup-team4435# | AC ✓ | 8ms | 3896kb | C++20 | 3.2kb | 2024-09-22 15:27:14 | 2024-10-14 07:52:41 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
--l;
while (r - l > 1) {
T mid = l + (r - l) / 2;
if (predicat(mid)) {
r = mid;
} else {
l = mid;
}
}
return r;
}
template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
return FindFirstTrue(l, r, predicat) - 1;
}
const ll INF = 2e18;
const int INFi = 1e9;
const int N = 2e5 + 5;
const int LG = 20;
void solve() {
int s, x; cin >> s >> x;
const int SZ = 3e3 + 5;
vector<bool> ok(SZ);
rep(i, SZ) ok[i] = (i == 0 || gcd(i, x) == 1);
vector<int> dp(SZ, INFi), prv(SZ, -1);
queue<int> q;
dp[0] = 0;
q.push(0);
while (!q.empty()) {
int v = q.front();
q.pop();
rep(u, SZ) {
if (dp[u] <= dp[v] + 1) continue;
if (ok[abs(u - v)]) {
dp[u] = dp[v] + 1;
prv[u] = u - v;
q.push(u);
}
}
}
int ans = INFi;
int f = -1;
const int MX = 1e9;
for(int diff = -SZ + 1; diff < SZ; ++diff) {
int val = s + diff;
if (abs(val) > MX) continue;
if (abs(gcd(val, x)) != 1) continue;
int total = dp[abs(diff)] + 1;
if (total < ans) {
ans = total;
f = val;
}
}
assert(ans < INFi);
vi res;
res.push_back(f);
s -= f;
ans--;
while (s != 0) {
assert(abs(s) < SZ);
assert(dp[abs(s)] == ans);
f = prv[abs(s)];
if (s < 0) {
res.push_back(-f);
s += f;
} else {
res.push_back(f);
s -= f;
}
ans--;
}
cout << res.size() << '\n';
for(auto &x : res) cout << x << ' ';
cout << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(12) << fixed;
int t = 1;
// cin >> t;
rep(i, t) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 3620kb
input:
9 6
output:
3 -2995 2999 5
result:
ok Correct
Test #2:
score: 0
Accepted
time: 6ms
memory: 3892kb
input:
14 34
output:
2 -2989 3003
result:
ok Correct
Test #3:
score: 0
Accepted
time: 7ms
memory: 3596kb
input:
1000000000 223092870
output:
2 999997007 2993
result:
ok Correct
Test #4:
score: 0
Accepted
time: 7ms
memory: 3840kb
input:
2 1000000000
output:
2 -3001 3003
result:
ok Correct
Test #5:
score: 0
Accepted
time: 8ms
memory: 3692kb
input:
649557664 933437700
output:
2 649554671 2993
result:
ok Correct
Test #6:
score: 0
Accepted
time: 7ms
memory: 3848kb
input:
33396678 777360870
output:
2 33393677 3001
result:
ok Correct
Test #7:
score: 0
Accepted
time: 7ms
memory: 3648kb
input:
48205845 903124530
output:
3 48202841 2987 17
result:
ok Correct
Test #8:
score: 0
Accepted
time: 7ms
memory: 3876kb
input:
251037078 505905400
output:
2 251034079 2999
result:
ok Correct
Test #9:
score: 0
Accepted
time: 7ms
memory: 3812kb
input:
30022920 172746860
output:
2 30019919 3001
result:
ok Correct
Test #10:
score: 0
Accepted
time: 7ms
memory: 3880kb
input:
63639298 808058790
output:
2 63636299 2999
result:
ok Correct
Test #11:
score: 0
Accepted
time: 7ms
memory: 3536kb
input:
76579017 362768406
output:
3 76576013 2999 5
result:
ok Correct
Test #12:
score: 0
Accepted
time: 7ms
memory: 3896kb
input:
40423669 121437778
output:
3 40420665 3001 3
result:
ok Correct
Test #13:
score: 0
Accepted
time: 3ms
memory: 3688kb
input:
449277309 720915195
output:
2 449274311 2998
result:
ok Correct
Test #14:
score: 0
Accepted
time: 7ms
memory: 3808kb
input:
81665969 919836918
output:
3 81662965 2999 5
result:
ok Correct
Test #15:
score: 0
Accepted
time: 7ms
memory: 3648kb
input:
470578680 280387800
output:
2 470575681 2999
result:
ok Correct
Test #16:
score: 0
Accepted
time: 6ms
memory: 3888kb
input:
58450340 803305503
output:
2 58447336 3004
result:
ok Correct
Test #17:
score: 0
Accepted
time: 7ms
memory: 3532kb
input:
125896113 323676210
output:
3 125893109 2987 17
result:
ok Correct
Test #18:
score: 0
Accepted
time: 7ms
memory: 3600kb
input:
381905348 434752500
output:
2 381902347 3001
result:
ok Correct
Test #19:
score: 0
Accepted
time: 7ms
memory: 3884kb
input:
78916498 653897673
output:
1 78916498
result:
ok Correct
Test #20:
score: 0
Accepted
time: 3ms
memory: 3532kb
input:
35787885 270845190
output:
3 35784883 3001 1
result:
ok Correct
Extra Test:
score: 0
Extra Test Passed