1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 #include using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair #define vi vector #define vll vector #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second pair solve_exp(vector g, int flip) { int n = SZ(g); vi best(n+1,n*n*3); vll cnt(n+1,0); if (flip) { FOR(i,n) FOR(j,n) if (i!=j) g[i][j] = 1-g[i][j]; } FOR(m,1< bad) { best[bit] = bad; cnt[bit] = 0; } if (best[bit] == bad) cnt[bit]++; } //cerr << "returning:\n"; //FOR(i,n+1) cerr << best[i] << " "; cerr << "\n"; //FOR(i,n+1) cerr << cnt[i] << " "; cerr << "\n"; return mp(best, cnt); } pair solve(vector g, int flip) { int n = SZ(g); vi best(n+1,n*n*3); vll cnt(n+1,0); if (n <= 14) { return solve_exp(g,flip); } best[0]=0; cnt[0]=1; flip = 1-flip; FOR(i,n) FOR(j,n) if (i!=j) g[i][j] = 1-g[i][j]; vi used(n); FOR(vv,n) if (!used[vv]) { queue q; vi comp; q.push(vv); comp.pb(vv); used[vv] = 1; while (!q.empty()) { int u = q.front(); q.pop(); FOR(i,n) if (g[i][u] && !used[i]) { //cerr << u+1 << " brings " << i+1 << "\n"; used[i] = 1; q.push(i); comp.pb(i); } } int m = SZ(comp); if (m == n) return solve_exp(g,flip); vector gc(m, vi(m,0)); FOR(i,m) FOR(j,m) gc[i][j] = g[comp[i]][comp[j]]; pair cur = solve(gc, flip); vi tbest(n+1,n*n*3); vll tcnt(n+1,0); tbest[0]=0; tcnt[0]=1; FOR(i,n+1) FOR(j,m+1) if (i+j <= n && i+j > 0) { int val = best[i] + cur.fi[j] + i*j*flip; //if (i+j == 1) cerr << i << " + " << j << " -> " << val << "\n"; if (val < tbest[i+j]) { tbest[i+j] = val; tcnt[i+j] = 0; } //if (i+j == 1) cerr << "cnt = " << tcnt[i+j] << "\n"; if (val == tbest[i+j]) tcnt[i+j] += cnt[i] * cur.se[j]; //if (i+j == 1) cerr << "cnt = " << tcnt[i+j] << "\n"; } best = tbest; cnt = tcnt; } //cerr << "returning:\n"; //FOR(i,n+1) cerr << best[i] << " "; cerr << "\n"; //FOR(i,n+1) cerr << cnt[i] << " "; cerr << "\n"; return mp(best, cnt); } const int N = 44; int a[N]; int main() { int n; scanf("%d", &n); FOR(i,n) scanf("%d", &a[i]); //FOR(i,n) a[i] = i+1; //random_shuffle(a,a+n); vector g(n, vi(n,0)); FOR(j,n) FOR(i,j) if (a[i] > a[j]) g[i][j] = g[j][i] = 1; pair res = solve(g, false); FORI(i,n) printf("%d %lld\n", res.fi[i], res.se[i]); return 0; }