QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#238788 | #7688. Alea Iacta Est | ucup-team055# | RE | 0ms | 3468kb | C++23 | 1.7kb | 2023-11-04 17:32:34 | 2023-11-04 17:32:35 |
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);
const ll sq = ceil(sqrt(N * M));
ll mn = INF;
pair<ll, ll> ab;
for(ll a : A) {
auto p = ranges::partition_point(B, [&](ll b) { return a * b < sq; });
if(a == N && *p == 1) if(++p == B.end()) continue;
if(a == 1 && *p == M) continue;
const ll b = *p;
if(chmin(mn, a * 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 <= 3e6);
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: 0ms
memory: 3468kb
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 6 1 2 3 2 3 4 3 1 4 7
result:
ok Correct. (3 test cases)
Test #2:
score: -100
Runtime Error
input:
1 40013 40013