QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#238816 | #7688. Alea Iacta Est | ucup-team055# | RE | 1ms | 3424kb | C++20 | 1.6kb | 2023-11-04 17:37:55 | 2023-11-04 17:37:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template <class T> bool chmin(T &a, T b) {
if (a <= b)
return 0;
a = b;
return 1;
}
template <class T> bool chmax(T &a, T b) {
if (a >= b)
return 0;
a = b;
return 1;
}
vector<ll> divisor(ll N) {
vector<ll> a, b;
ll d = 1;
for (; d * d < N; d++)
if (N % d == 0) {
a.push_back(d);
b.push_back(N / d);
}
if (d * d == N)
a.push_back(d);
a.insert(a.end(), b.rbegin(), b.rend());
return a;
}
ll sumf = 0;
void solve() {
ll N, M;
cin >> N >> M;
if (N > M)
swap(N, M);
auto A = divisor(N), B = divisor(M);
ll mn = INF;
pair<ll, ll> ab;
for (ll a : A) {
for (ll b : B) {
if (a == 1 && b == M)
continue;
if (a == N && b == 1)
continue;
if (chmin(mn, a * b + (N / a) * (M / b)))
ab = {a, b};
}
}
if (mn == INF) {
cout << "0\n";
return;
}
const auto [a, b] = ab;
const ll c = N / a, d = M / b;
sumf += a * b + c * d;
assert(sumf <= 5e6);
vector<ll> ans1, ans2;
rep(i, 0, a) rep(j, 0, b) ans1.push_back(i + j + 1);
rep(i, 0, c) rep(j, 0, d) ans2.push_back(i * a + j * b + 1);
auto out = [](vector<ll> a) {
cout << a.size();
for (ll x : a)
cout << ' ' << x;
cout << '\n';
};
out(ans1);
out(ans2);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
ll T;
cin >> T;
while (T--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3424kb
input:
3 2 8 1 9 2 9
output:
4 1 2 3 4 4 1 5 2 6 3 1 2 3 3 1 4 7 3 1 2 3 6 1 4 7 2 5 8
result:
ok Correct. (3 test cases)
Test #2:
score: -100
Runtime Error
input:
1 40013 40013