QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#239854#7688. Alea Iacta Estucup-team1191#TL 0ms3688kbC++2012.4kb2023-11-04 23:57:142023-11-04 23:57:14

Judging History

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

  • [2023-11-04 23:57:14]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3688kb
  • [2023-11-04 23:57:14]
  • 提交

answer

/*
    author:  Maksim1744
    created: 04.11.2023 18:36:27
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

struct Factorizer {
    // Factorizer factorizer(prec_n, sp_bound, rng_seed);
    //    prec_n is the bound for sieve (inclusive)
    //    all numbers will first be checked on primes <= sp_bound (if prec_n >= sp_bound)
    //    factorization for one number ~1e18 takes ~13ms

    vector<int> min_prime;
    vector<int> primes;
    int prec_n;
    int sp_bound;

    Factorizer(int prec_n = 100, int sp_bound = 100, int64_t rng_seed = -1) :
        prec_n(max(prec_n, 3)),
        sp_bound(sp_bound),
        rng(rng_seed != -1 ? rng_seed : chrono::steady_clock::now().time_since_epoch().count()) {
        min_prime.assign(prec_n + 1, -1);
        for (int i = 2; i <= prec_n; ++i) {
            if (min_prime[i] == -1) {
                min_prime[i] = i;
                primes.push_back(i);
            }
            int k = min_prime[i];
            for (int j : primes) {
                if (j * i > prec_n) break;
                min_prime[i * j] = j;
                if (j == k) break;
            }
        }
    }

    bool is_prime(int64_t n, bool check_small = true) {
        if (n <= prec_n)
            return min_prime[n] == n;

        if (check_small) {
            for (int p : primes) {
                if (p > sp_bound || (int64_t)p * p > n) break;
                if (n % p == 0) return false;
            }
        }

        int s = 0;
        int64_t d = n - 1;
        while (d % 2 == 0) {
            ++s;
            d >>= 1;
        }
        for (int64_t a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
            if (a >= n) break;
            int64_t x = mpow_long(a, d, n);
            if (x == 1 || x == n - 1)
                continue;
            bool composite = true;
            for (int i = 0; i < s - 1; ++i) {
                x = mul_mod(x, x, n);
                if (x == 1)
                    return false;
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite)
                return false;
        }
        return true;
    }

    vector<pair<int64_t, int>> factorize(int64_t n, bool check_small = true) {
        vector<pair<int64_t, int>> res;
        if (check_small) {
            for (int p : primes) {
                if (p > sp_bound) break;
                if ((int64_t)p * p > n) break;
                if (n % p == 0) {
                    res.emplace_back(p, 0);
                    while (n % p == 0) {
                        n /= p;
                        res.back().second++;
                    }
                }
            }
        }

        if (n == 1) return res;
        if (is_prime(n, false)) {
            res.emplace_back(n, 1);
            return res;
        }

        if (n <= prec_n) {
            while (n != 1) {
                int d = min_prime[n];
                if (res.empty() || res.back().first != d)
                    res.emplace_back(d, 0);
                res.back().second++;
                n /= d;
            }
            return res;
        }

        int64_t d = get_divisor(n);
        auto a = factorize(d, false);
        for (auto &[div, cnt] : a) {
            cnt = 0;
            while (n % div == 0) {
                n /= div;
                ++cnt;
            }
        }
        auto b = factorize(n, false);

        int ia = 0, ib = 0;
        while (ia < a.size() || ib < b.size()) {
            bool choosea;
            if (ia == a.size()) choosea = false;
            else if (ib == b.size()) choosea = true;
            else if (a[ia].first <= b[ib].first) choosea = true;
            else choosea = false;

            res.push_back(choosea ? a[ia++] : b[ib++]);
        }
        return res;
    }

  private:
    mt19937_64 rng;
    int64_t rnd(int64_t l, int64_t r) {
        return uniform_int_distribution<int64_t>(l, r)(rng);
    }

    int64_t mpow_long(int64_t a, int64_t p, int64_t mod) {
        int64_t res = 1;
        while (p) {
            if (p & 1) res = mul_mod(res, a, mod);
            p >>= 1;
            a = mul_mod(a, a, mod);
        }
        return res;
    }

    int64_t mul_mod(int64_t a, int64_t b, int64_t mod) {
        int64_t res = a * b - mod * (int64_t)((long double)1 / mod * a * b);
        if (res < 0) res += mod;
        if (res >= mod) res -= mod;
        return res;
    }

    int64_t get_divisor(int64_t n) {
        auto f = [&](int64_t x) -> int64_t {
            int64_t res = mul_mod(x, x, n) + 1;
            if (res == n) res = 0;
            return res;
        };

        while (true) {
            int64_t x = rnd(1, n - 1);
            int64_t y = f(x);
            while (x != y) {
                int64_t d = gcd(n, abs(x - y));
                if (d == 0)
                    break;
                else if (d != 1)
                    return d;
                x = f(x);
                y = f(f(y));
            }
        }
    }
};

Factorizer factorizer;

void test_case(int test) {
    ll n, m;
    cin >> n >> m;
    ll nm = n * m;
    vector<ll> divs;
    for (ll d = 1; d * d <= nm; ++d) {
        if (nm % d == 0) {
            divs.pb(d);
        }
    }
    reverse(divs.begin(), divs.end());
    auto get_divs = [&](ll n) -> vector<ll> {
        vector<ll> d = {1};
        for (const auto& [p, c] : factorizer.factorize(n)) {
            int sz = d.size();
            ll pw = 1;
            for (int i = 0; i < c; ++i) {
                pw *= p;
                for (int j = 0; j < sz; ++j) {
                    d.pb(d[j] * pw);
                }
            }
        }
        return d;
    };
    vector<ll> poly0(n + m - 1);
    for (int i = 0; i < poly0.size(); ++i) {
        ll d = min(i, (int)poly0.size() - 1 - i) + 1;
        poly0[i] = min({d, n, m});
    }
    show(poly0);

    auto div_by = [&](vector<ll>& a, ll p) -> bool {
        // divide by x^p - 1
        if (a.size() < p) return false;
        for (int i = (int)a.size() - 1; i >= p; --i) {
            a[i - p] += a[i];
        }
        reverse(a.begin(), a.end());
        for (int i = (int)a.size() - p; i < a.size(); ++i)
            if (a[i] != 0)
                return false;
        a.resize(a.size() - p);
        reverse(a.begin(), a.end());
        return true;
    };

    auto mul_by = [&](vector<ll>& a, ll p) {
        // multiply by x^p - 1
        a.resize(a.size() + p, 0);
        for (int i = (int)a.size() - 1 - p; i >= 0; --i) {
            a[i + p] += a[i];
            a[i] *= -1;
        }
        return a;
    };

    // if (n == 1 && m == 1) {
    //     cout << "2 1 1\n";
    //     cout << "1 1\n";
    //     return;
    // }

    // mul_by(poly0, 3);
    // div_by(poly0, 3);
    // show(poly0);

    for (ll sa : divs) {
        auto pers = get_divs(sa);
        sort(pers.begin(), pers.end());
        for (ll c : pers) {
            ll trap_sum = sa / c;
            for (ll h : pers) {
                ll triangle_sum = h * h;
                if (triangle_sum > trap_sum) break;
                ll extra = trap_sum - triangle_sum;
                assert(extra % h == 0);
                extra /= h;
                // vector<ll> a;
                // auto add = [&](ll u) {
                //     for (int i = 0; i < c; ++i) {
                //         a.pb(u);
                //     }
                // };
                // for (int u = 1; u <= x; ++u) {
                //     add(u);
                // }
                // for (int i = 0; i < extra; ++i) {
                //     add(x);
                // }
                // for (int u = x - 1; u >= 1; ++u) {
                //     add(u);
                // }
                // ac + bc + c - 1 - 2c == alen
                ll alen = (h * 2 - 1 + extra) * c;
                ll a = h;
                ll b = a + extra;
                if (a == 1 && (b * c == n || b * c == m)) continue;
                assert(a * c + b * c + c - 1 - c * 2 == alen - 1);
                show(n, m);
                show(h, extra, sa);
                show(a, b, c);
                auto p = poly0;
                mul_by(p, 1);
                mul_by(p, c);
                // mul_by(p, c);
                if (!div_by(p, a * c)) continue;
                if (!div_by(p, b * c)) continue;
                if (mine(p) < 0) continue;
                {
                    vector<ll> a;
                    auto add = [&](ll u) {
                        for (int i = 0; i < c; ++i) {
                            a.pb(u);
                        }
                    };
                    for (int u = 1; u <= h; ++u) {
                        add(u);
                    }
                    for (int i = 0; i < extra; ++i) {
                        add(h);
                    }
                    for (int u = h - 1; u >= 1; ++u) {
                        add(u);
                    }

                    auto print = [&](const vector<ll>& v) {
                        vector<int> res;
                        for (int i = 0; i < v.size(); ++i) {
                            for (int j = 0; j < v[i]; ++j) {
                                res.pb(i + 1);
                            }
                        }
                        cout << res.size() << ' ' << res << '\n';
                    };

                    print(a);
                    print(p);
                    return;
                }
            }
        }
    }
    if (n > m) swap(n, m);
    cout << n * 2;
    for (int i = 0; i < n; ++i) {
        cout << ' ' << i + 1 << ' ' << i + 1;
    }
    cout << '\n';
    cout << m << ' ';
    for (int i = 0; i < m; ++i) {
        cout << i + 1 << ' ';
    }
    cout << '\n';
    // assert(false);
    // cout << "0\n0\n";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T;
    cin >> T;
    for (int test = 1; test <= T; ++test) {
        test_case(test);
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3688kb

input:

3
2 8
1 9
2 9

output:

4 1 2 3 4 
4 1 2 5 6 
3 1 2 3 
3 1 4 7 
3 1 2 3 
6 1 2 4 5 7 8 

result:

ok Correct. (3 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

1
40013 40013

output:


result: