QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#238816#7688. Alea Iacta Estucup-team055#RE 1ms3424kbC++201.6kb2023-11-04 17:37:552023-11-04 17:37:55

Judging History

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

  • [2023-11-04 17:37:55]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3424kb
  • [2023-11-04 17:37:55]
  • 提交

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

output:


result: