Skip to content

Instantly share code, notes, and snippets.

@anta0
Last active August 29, 2015 14:11
Show Gist options
  • Save anta0/48e0f2a20edda705c851 to your computer and use it in GitHub Desktop.
Save anta0/48e0f2a20edda705c851 to your computer and use it in GitHub Desktop.
Brasil National Programming Challenge
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
struct MaximumFlow {
typedef int Index;
typedef int Flow;
static const Flow InfCapacity = INF;
struct Edge {
Index to;
Flow capacity;
Index rev;
};
vector<vector<Edge> > g;
void init(Index n) { g.assign(n, vector<Edge>()); }
void add(Index i, Index j, Flow capacity) {
Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0;
g[i].push_back(e); g[j].push_back(f);
g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
}
void addB(Index i, Index j, Flow capacity) {
Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = capacity;
g[i].push_back(e); g[j].push_back(f);
g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
}
//g?????
Flow maximumFlow(int s, int t) {
int n = g.size();
vector<Index> level(n);
Flow total = 0; bool update;
do {
update = false;
fill(level.begin(), level.end(), -1); level[s] = 0;
queue<Index> q; q.push(s);
for(Index d = n; !q.empty() && level[q.front()] < d; ) {
int u = q.front(); q.pop();
if(u == t) d = level[u];
each(e, g[u]) if(e->capacity > 0 && level[e->to] == -1)
q.push(e->to), level[e->to] = level[u] + 1;
}
vector<Index> iter(n);
for(Index i = 0; i < n; i ++) iter[i] = (int)g[i].size() - 1;
while(1) {
Flow f = augment(level, iter, s, t, InfCapacity);
if(f == 0) break;
total += f; update = true;
}
}while(update);
return total;
}
Flow augment(vector<Index> &level, vector<Index> &iter, Index u, Index t, Flow f) {
if(u == t || f == 0) return f;
Index lv = level[u];
if(lv == -1) return 0;
level[u] = -1;
for(; iter[u] >= 0; -- iter[u]) {
Edge &e = g[u][iter[u]];
if(level[e.to] <= lv) continue;
Flow l = augment(level, iter, e.to, t, min(f, e.capacity));
if(l == 0) continue;
e.capacity -= l; g[e.to][e.rev].capacity += l;
level[u] = lv;
return l;
}
return 0;
}
};
int main() {
int n;
scanf("%d", &n);
const int D = 1000;
vector<int> blue(D, 0), yellow(D, 0);
rep(i, n) {
int c, d;
scanf("%d%d", &c, &d), -- c, -- d;
if(c == 0) {
++ blue[d];
}else {
++ yellow[d];
}
}
int s = D * 2, t = s + 1;
MaximumFlow mf;
mf.init(t + 1);
rep(d, D)
mf.add(s, d, blue[d]);
rer(x, 1, D) rer(y, 1, D) {
int xx = x * x, yy = y * y;
if(xx < 2 * yy && yy < 2 * xx)
mf.add(x - 1, D + (y - 1), INF);
}
rep(d, D)
mf.add(D + d, t, yellow[d]);
int ans = mf.maximumFlow(s, t);
printf("%d\n", ans);
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
struct UnionFind {
vector<int> data;
void init(int n) { data.assign(n, -1); }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if(x != y) {
if(data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) { return root(x) == root(y); }
int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
int size(int x) { return -data[root(x)]; }
};
int main() {
int T;
scanf("%d", &T);
rep(ii, T) {
int H, W;
scanf("%d%d", &H, &W);
vector<vector<bool> > ground(H, vector<bool>(W));
rep(i, H) rep(j, W) {
int g;
scanf("%d", &g);
ground[i][j] = g != 0;
}
UnionFind uf; uf.init(H * W);
rep(i, H) rep(j, W) if(ground[i][j]) {
rer(dy, -1, 1) rer(dx, -1, 1) if(dy || dx) {
int yy = i + dy, xx = j + dx;
if(!(0 <= yy && yy < H && 0 <= xx && xx < W)) continue;
if(ground[yy][xx])
uf.unionSet(i * W + j, yy * W + xx);
}
}
int ans1 = 0, ans2 = 0;
rep(i, H) rep(j, W) if(ground[i][j]) {
ans1 += uf.root(i * W + j) == i * W + j;
amax(ans2, uf.size(i * W + j));
}
printf("%d %d\n", ans1, ans2);
}
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt(): x(0) { }
ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;
int main() {
int T;
scanf("%d", &T);
rep(ii, T) {
int N, M;
scanf("%d%d", &N, &M);
vector<int> L(N), C(N);
rep(i, N)
scanf("%d%d", &L[i], &C[i]), -- L[i], -- C[i];
vector<vi> g(N);
rep(i, N) if(L[i] != -1)
g[L[i]].push_back(i);
vi A;
rep(i, N) if(L[i] == -1) {
if(!A.empty()) return 1;
int j = i;
while(1) {
A.push_back(C[j]);
if(g[j].empty()) break;
if(g[j].size() != 1) return 1;
j = g[j][0];
}
}
if(A.size() != N) return 1;
const int X = 1000;
mint ans = 0;
vector<vector<mint> > dp(X, vector<mint>(M+1, 0));
vector<mint> sums(M+1, 0);
sums[0] = 1;
rep(i, N) {
int a = A[i];
for(int j = M; j >= 1; -- j) {
mint t = sums[j-1];
t -= dp[a][j];
dp[a][j] += t;
sums[j] += t;
ans += t;
}
}
printf("%d\n", ans.get());
}
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
int sq(int x) { return x*x; }
int main() {
const int W = 1000;
vector<vi> cnt(W+1, vector<int>(W+1, 0));
int N;
scanf("%d", &N);
rep(ii, N) {
int X, Y, R;
scanf("%d%d%d", &X, &Y, &R);
int rr = R * R;
rer(y, 1, W) rer(x, 1, W) {
int d = sq(x-X) + sq(y-Y);
if(d <= rr)
++ cnt[y][x];
}
}
int ans = 0;
rer(y, 1, W) rer(x, 1, W)
ans += cnt[y][x] >= 2;
printf("%d\n", ans);
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <unordered_map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
template<typename T>T gcd(T x, T y){if(y==0)return x;else return gcd(y,x%y);}
vector<bool> isprime;
vector<int> primes;
void sieve(int n){
if((int)isprime.size() >= n+1) return;
isprime.assign(n+1, true);
isprime[0] = isprime[1] = false;
int sqrtn = (int)(sqrt(n * 1.) + .5);
for(int i = 2; i <= sqrtn; i ++) if(isprime[i]) {
for(int j = i * i; j <= n; j += i)
isprime[j] = false;
}
primes.clear();
for(int i = 2; i <= n; i ++) if(isprime[i])
primes.push_back(i);
}
inline long long mulmodll(long long a, long long b, long long m) {
long long quot, res;
const unsigned HALF_OF_ONE = 0x3f000000;
#ifdef __GNUC__
//80bit???????????????
//#pragma STDC FENV_ACCESS on
// unsigned short fcw;
// asm ("fnstcw %0;" : "=m" (fcw));
// unsigned short fcw_s = fcw;
// fcw |= 3<<8;
// asm ("fldcw %0;" : : "m" (fcw));
asm (
"fildq %1;\n\t"
"fildq %2;\n\t"
"fmulp;\n\t"
"fildq %3;\n\t"
"fdivrp;\n\t"
"fadd %4;\n\t"
"fisttpq %0;"
: "=m" (quot)
: "m" (a), "m" (b), "m" (m), "m"(HALF_OF_ONE)
: "st(2)"
);
// asm ("fldcw %0;" : : "m" (fcw_s));
//#pragma STDC FENV_ACCESS off
#else
#pragma STDC FENV_ACCESS on
unsigned short fcw;
//??80bit????????
__asm {
fnstcw word ptr [fcw];
mov ax, [fcw];
or word ptr [fcw], 3<<8;
fldcw word ptr [fcw];
fild qword ptr [a];
fild qword ptr [b];
fmulp st(1), st(0);
fild qword ptr [m];
fdivp st(1), st(0);
fadd dword ptr [HALF_OF_ONE];
fisttp qword ptr [quot];
mov [fcw], ax;
fldcw word ptr [fcw];
};
#pragma STDC FENV_ACCESS off
#endif
res = a * b - m * quot;
if(res < 0) res += m;
return res;
}
long long powmodll(long long a, long long k, long long MOD) {
unsigned long long r = MOD == 1 ? 0 : 1;
while(k) {
if(k & 1)
r = mulmodll(r, a, MOD);
a = mulmodll(a, a, MOD);
k >>= 1;
}
return r;
}
#ifdef WIN32
extern "C" int __stdcall QueryPerformanceFrequency(long long*);
extern "C" int __stdcall QueryPerformanceCounter(long long*);
double getTime() {
long long c, freq;
QueryPerformanceCounter(&c);
QueryPerformanceFrequency(&freq);
return c * 1. / freq;
}
#else
#include <sys/time.h>
double getTime() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1e6;
}
#endif
typedef long long FactorsInt;
typedef vector<pair<FactorsInt,int> > Factors;
template<typename Op> inline Factors combineFactors(Op op, int id, const Factors &a, const Factors &b) {
Factors c;
int an = a.size(), bn = b.size();
int ai = 0, bi = 0;
while(ai < an || bi < bn) {
typename Factors::value_type::first_type p; int q;
if(ai < an && (bi >= bn || a[ai].first < b[bi].first)) {
p = a[ai].first, q = op(a[ai].second, id);
ai ++;
}else if(bi < bn && (ai >= an || a[ai].first > b[bi].first)) {
p = b[bi].first, q = op(id, b[bi].second);
bi ++;
}else {
p = a[ai].first, q = op(a[ai].second, b[bi].second);
ai ++, bi ++;
}
if(q != 0) c.push_back(mp(p, q));
}
return c;
}
Factors productFactors(const Factors &a, const Factors &b) {
return combineFactors(std::plus<int>(), 0, a, b);
}
long long pollardRho(long long n, int seed) {
if(n <= 1) return -1;
if(n > 2 && n % 2 == 0) return 2;
seed %= n;
long long x = 2;
for(long long j = 1; ; j <<= 1) {
long long y = x;
for(int i = 0; i < j; ++ i) {
if((x = (mulmodll(x, x, n) + seed) >= n)) x -= n;
long long d = gcd(abs(x - y), n);
if(d != 1) return d < n ? d : -1;
}
}
}
bool millarRabin(long long n) {
if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
int test[] = {2,3,5,7,11,13,17,19,23,-1};
long long d = n - 1; int s = 0;
while (d % 2 == 0) ++ s, d /= 2;
for(int i = 0; ; ++i) {
long long a = test[i];
if(a == -1 || a >= n) break;
long long x = powmodll(a, d, n);
if(x == 1) continue;
int r;
for(r = 0; r < s; ++r) {
if(x == n - 1) break;
x = mulmodll(x, x, n);
}
if(r == s) return false;
}
return true;
}
void factor(long long X, Factors &factors) {
factors.clear();
if(millarRabin(X)) {
factors.push_back(mp(X, 1));
return;
}
each(pt, primes) {
int p = *pt;
if((long long)p * p > X) break;
if(X % p != 0) continue;
X /= p;
int k = 1;
while(X % p == 0) {
++ k;
X /= p;
}
factors.push_back(mp(p, k));
}
if(X == 1) return;
if(millarRabin(X)) {
factors.push_back(mp(X, 1));
return;
}
rep(iter, 1000) {
long long d = pollardRho(X, iter);
if(d != -1) {
Factors a;
factor(d, a);
factors = productFactors(factors, a);
X /= d;
if(millarRabin(X)) {
factors.push_back(mp(X, 1));
return;
}
}
}
// cerr << "failed to factor: " << X << endl;
factors.push_back(mp(X, 1));
}
long long powk(long long x, int k) {
long long r = x;
rep(i, k-1)
r *= x;
return r;
}
int rooti(long long x, int k) {
if(k <= 1) return -1;
int r;
if(k == 2) r = (int)sqrt(x * 1.L);
else if(k == 3) r = (int)cbrt(x * 1.L);
else r = (int)pow(x * 1.L, 1.L / k);
long long p = powk(r, k);
if(p > x) {
do -- r; while(powk(r, k) > x);
}else {
while(powk(r+1, k) <= x) ++ r;
}
return r;
}
bool perfectPower(long long x, int &y, int &k) {
rer(i, 2, 10) {
int r = rooti(x, i);
if(powk(r, i) == x) {
y = r, k = i;
return true;
}
}
y = k = -1;
return false;
}
const int MaxK = 60;
char gcdTable[MaxK+1][MaxK+1];
vi powerChains[MaxK+1];
void powerChain(int x, vector<int> &v) {
if(x == 1) return;
int y, k;
if(!perfectPower(x, y, k)) {
v.push_back(x);
}else {
powerChain(y, v);
v.push_back(k);
}
}
struct Xor128 {
unsigned x, y, z, w;
Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
unsigned next() {
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
unsigned long long nextll() {
unsigned long long x = (unsigned long long)next() << 32;
return x | next();
}
} xor128;
vector<vector<long long> > bestsubarrays;
int bestN; int bestM;
Factors factors;
double timeLimit;
vector<vector<char> > representparts;
vector<char> curparts;
vector<vector<char> > partssets;
vector<char> exponentdivisors;
unordered_map<unsigned,int> memo[61];
unsigned cnthashseed[61];
unsigned cnthash;
int curN = 0;
void findPartitions2rec(vector<char> &counts);
void findPartitions2rec2(int i, int g, vector<char> &counts) {
if(i < g) {
if(curparts.empty())
return;
partssets.push_back(curparts);
curparts.clear();
findPartitions2rec(counts);
curparts = partssets.back();
partssets.pop_back();
return;
}
if((int)counts.size() > i && counts[i] > 0) {
char pt = representparts[i].back();
-- counts[i], representparts[i].pop_back(), cnthash -= cnthashseed[i];
++ counts[i-g], representparts[i-g].push_back(pt), cnthash += cnthashseed[i-g];
curparts.push_back(pt);
int poppedback = 0;
while(counts.size() > 1 && counts.back() == 0)
counts.pop_back(), ++ poppedback;
findPartitions2rec2(i, g, counts);
rep(k, poppedback)
counts.push_back(0);
curparts.pop_back();
-- counts[i-g], representparts[i-g].pop_back(), cnthash -= cnthashseed[i-g];
++ counts[i], representparts[i].push_back(pt), cnthash += cnthashseed[i];
}
findPartitions2rec2(i-1, g, counts);
}
void findPartitions2rec(vector<char> &counts) {
int &memoized = memo[partssets.size()][cnthash];
if(memoized >= curN) return;
memoized = curN;
if(counts.size() == 1) {
int N = curN, M = partssets.size();
if(bestN * M < N * bestM) {
bestsubarrays.clear();
rep(i, partssets.size()) {
const vector<char> &s = partssets[i];
int g = exponentdivisors[i];
long long prod = 1;
each(j, s) prod *= factors[*j].first;
vector<long long> v;
v.push_back(prod);
v.insert(v.end(), all(powerChains[g]));
bestsubarrays.push_back(v);
}
bestN = N, bestM = M;
/*
cerr << "[";
each(i, bestsubarrays) {
if(i != bestsubarrays.begin()) cerr << "], [";
each(j, *i) {
if(j != i->begin()) cerr << ", ";
cerr << *j;
}
}
cerr << "]: " << N << " / " << M << " (" << N * 1. / M << ")" << endl;
// */
}
return;
}
for(int g = counts.size()-1; g >= 1; -- g) {
exponentdivisors.push_back(g);
curN += 1 + powerChains[g].size();
findPartitions2rec2(counts.size()-1, g, counts);
curN -= 1 + powerChains[g].size();
exponentdivisors.pop_back();
}
}
void findPartitions2() {
int K = 0;
each(i, factors) amax(K, i->second);
representparts.assign(K+1, vector<char>());
vector<char> counts(K+1, 0);
cnthash = 0;
each(i, factors) {
++ counts[i->second];
representparts[i->second].push_back(i - factors.begin());
}
rep(k, 61) memo[k].clear();
rer(i, 0, K)
cnthash += cnthashseed[i] * counts[i];
memo[0][cnthash] = -1;
findPartitions2rec(counts);
}
int main() {
cnthashseed[0] = 1;
rer(i, 1, 60)
cnthashseed[i] = i * 1000000007;
double absoluteLimit = getTime() + 2.;
sieve(100000);
rer(x, 0, MaxK) rer(y, 0, MaxK)
gcdTable[x][y] = (char)gcd(x, y);
rer(k, 1, MaxK)
powerChain(k, powerChains[k]);
int T;
scanf("%d", &T);
rep(ii, T) {
long long X;
scanf("%lld", &X);
timeLimit = getTime() + (absoluteLimit - getTime()) / (T - ii) * 0.99;
// X = xor128.nextll() % ((ll)1e18-1) + 2;
if(X <= 1 || X > (ll)1e18) {
cerr << "error X = " << X << endl;
continue;
}
factor(X, factors);
// cerr << "factor: "; each(i, factors) cerr << (i==factors.begin()?"":" * ") << i->first << "^" << i->second; cerr << endl;
bestN = -1, bestM = 1;
findPartitions2();
{ vector<long long> A;
vector<int> L, R;
int offset = 0;
each(i, bestsubarrays) {
each(j, *i)
A.push_back(*j);
L.push_back(offset);
offset += i->size();
R.push_back(offset);
}
int N = A.size(), M = L.size();
printf("%d %d\n", N, M);
rep(i, N) {
if(i != 0) putchar(' ');
printf("%lld", A[i]);
}
puts("");
rep(i, M)
printf("%d %d\n", L[i] + 1, R[i]);
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment