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 #include #include #include using namespace std; vector> v; int n,a,wyn, CL; int N[32]; int ile[32]; int best[32]; int perm[32]; int main() { //n = 29; scanf("%d", &n); for(int i = 0; i <= n; i++) perm[i] = i; random_shuffle(perm + 1, perm + n + 1); for(int i = 1; i <= n; i++) { scanf("%d", &a); //a = perm[i]; v.emplace_back(a, i); } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(v[i].first < v[j].first && v[i].second < v[j].second) { N[i] |= (1ll << j); N[j] |= (1ll << i); } } } int MASK = 0; int K = 0; int wyn = 0; int mov, boi; int LIM = (1ll << n); bool negate; for(int I = 1; I ^ LIM; ++I) { mov = I & (-I); boi = __builtin_ctz(mov); MASK ^= mov; negate = !(MASK & mov); K += (1 ^ -negate) + negate; wyn += (__builtin_popcount(N[boi] & MASK) ^ -negate) + negate; if(wyn >= best[K]) { if(wyn > best[K]) { best[K] = wyn; ile[K] = 0; } ++ile[K]; } } for(int i = 1; i <= n; i++) { printf("%d %d\n", i * (i - 1) / 2 - best[i], ile[i]); } }