This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void merge(vector<int> &a, vector<int> &b) {
for (int x: b) {
a.push_back(x);
}
}
void rollback(vector<int>& a, int x) {
while (x--) {
a.pop_back();
}
}
const int N = 15;
int a[N], ans[N];
int s, n, m;
void rec(int L, int R, vector<vector<int>> &g) {
if (L == s && R == s + 1) {
for (int c1 = 0; c1 < m; ++c1) {
for (int c2 = 0; c2 < m; ++c2) {
int now = 0;
for (int x: g[s]) {
now += a[x] != c1;
}
for (int x: g[s + 1]) {
now += a[x] != c2;
}
ans[c1] = min(ans[c1], now);
ans[c2] = min(ans[c2], now);
}
}
return;
}
for (int i = L + 1; i <= s; ++i) {
if (i + (i - L) - 1 > R) {
break;
}
for (int j = L; j < i; ++j) {
merge(g[i + (i - j) - 1], g[j]);
}
rec(i, R, g);
for (int j = L; j < i; ++j) {
rollback(g[i + (i - j) - 1], g[j].size());
}
}
for (int i = R - 1; i >= s + 1; --i) {
if (i - (R - i) + 1 < s) {
break;
}
for (int j = R; j > i; --j) {
merge(g[i - (j - i) + 1], g[j]);
}
rec(L, i, g);
for (int j = R; j > i; --j) {
rollback(g[i - (j - i) + 1], g[j].size());
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(ans, 0x3f, sizeof(ans));
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
--a[i];
}
vector g(n, vector<int>(1));
for (int i = 0; i < n; ++i) {
g[i][0] = i;
}
for (s = 0; s < n - 1; ++s) {
rec(0, n - 1, g);
}
for (int i = 0; i < m; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |