QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#239854 | #7688. Alea Iacta Est | ucup-team1191# | TL | 0ms | 3688kb | C++20 | 12.4kb | 2023-11-04 23:57:14 | 2023-11-04 23:57:14 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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