QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#238774#7688. Alea Iacta Estucup-team055#RE 0ms3620kbC++231.7kb2023-11-04 17:29:482023-11-04 17:29:48

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 17:29:48]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3620kb
  • [2023-11-04 17:29:48]
  • 提交

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) {
        auto p = ranges::partition_point(B, [&](ll b) { return a * b * a * b < N * M; });
        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: 3620kb

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

output:


result: