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 116 117 118 119 120 121 122 123 124 125 126 #include #include #include #include #include #include #include #include #include using namespace std; int perm[42]; using Arr = array; struct Vert { int group_size; int pos; Arr arr; Vert(int group_size, int pos, Arr arr):group_size(group_size),pos(pos),arr(arr) {} bool operator<(const Vert& o) const { return make_pair(pos, make_pair(group_size, arr)) < make_pair(o.pos, make_pair(o.group_size, o.arr)); } bool operator==(const Vert& o) const { return pos == o.pos && o.group_size == group_size && o.arr == arr; } }; struct vert_hash { unsigned operator()(const Vert& v) const { unsigned a = v.group_size; for (uint8_t i : v.arr) { a *= 31; a += i; } return a; } }; const int MAX_INV = 900; int N; void solve() { unordered_map q[MAX_INV][41]; Arr initial_values {}; for (int pos=0; pos <= 0/*N*/; pos ++) q[0][pos][Vert(0, pos, initial_values)]++; pair best[41]; for (int i=0; i < 41; i++) best[i] = make_pair(10000000, -1); bool finish = false; int tot = 0; for (int qpos=0; qpos < MAX_INV; qpos ++) { if (finish) break; for (int setpos=0; setpos <= N; setpos ++) { //cerr << "size " << q[qpos][setpos].size() << " " << qpos << "x" << setpos << " " << tot << endl; for (auto it : q[qpos][setpos]) { tot ++; //Vert v = q[qpos][setpos].begin()->first; //long long mult = q[qpos][setpos].begin()->second; Vert v = it.first; long long mult = it.second; assert(setpos == v.pos); if (v.group_size == N) { finish = true; } if (v.pos == N) continue; //for (int i=0; i < v.pos; i++) assert(v.arr[i]==0); //q[qpos].emplace_back(v.group_size, v.pos + 1, v.arr); // next Arr new_values = v.arr; for (int i=v.pos+1; i < N; i++) { if (perm[v.pos] > perm[i]) new_values[i] ++; } for (int i=0; i < v.pos+1; i++) { new_values[i]=0; } int t_group_size = v.group_size+1; if (t_group_size > N) abort(); int tcost = qpos + v.arr[v.pos]; if (tcost <= best[t_group_size].first) { if (tcost == best[t_group_size].first) { best[t_group_size].second += mult; } else { best[t_group_size] = make_pair(tcost, mult); } } for (int pos = v.pos + 1; pos <= v.pos + 1/*N*/; pos ++) { // what if v.arr[v.pos] == 0! assert(pos > setpos); new_values[pos-1] = 0; q[qpos + v.arr[v.pos]][pos][Vert(v.group_size + 1, pos, new_values)] += mult; } // this new_values = v.arr; new_values[v.pos] = 0; int pos = v.pos + 1; q[qpos][pos][Vert(v.group_size, pos, new_values)] += mult; } q[qpos][setpos].clear(); //cerr << "tot " << tot << " " << endl; } } for (int i=1; i <= N; i++) { cout << best[i].first << " " << best[i].second << "\n"; } //cout << "fin" << endl; } int main() { ios_base::sync_with_stdio(0); cin >> N; for(int i=0;i>perm[i]; perm[i]--; } solve(); }