Submission #489165

#TimeUsernameProblemLanguageResultExecution timeMemory
489165cheissmartRope (JOI17_rope)C++14
45 / 100
2586 ms25696 KiB
#include <bits/stdc++.h> #define IO_OP ios::sync_with_stdio(0), cin.tie(0) #define F first #define S second #define V vector #define PB push_back #define EB emaplce_back #define MP make_pair #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef vector<int> vi; const int INF = 1e9 + 7, N = 1e6 + 7; int a[N], ans[N]; vi pos[N]; void cmin(int& a, int b) { a = min(a, b); } signed main() { IO_OP; int n, m; cin >> n >> m; for(int i = 0; i < n; i++) { cin >> a[i]; a[i]--; pos[a[i]].PB(i); } auto go = [&] (int x, int y) { vi c; int pre = -1, lazy = 0; auto fillin = [&] (int nxt) { // pre + 1, ... nxt - 1 int len = (nxt - 1) - (pre + 1) + 1; if(len) { len %= 8; if(len == 0) len = 8; for(int i = 0; i < len; i++) c.PB(-1); } }; for(int i = 0, j = 0; i < int(pos[x].size()) || j < int(pos[y].size());) { if(j == int(pos[y].size()) || (i < int(pos[x].size()) && pos[x][i] < pos[y][j])) { fillin(pos[x][i]); pre = pos[x][i]; c.PB(x); i++; } else { fillin(pos[y][j]); pre = pos[y][j]; c.PB(y); j++; } } fillin(n); lazy = n - int(c.size()); int n = int(c.size()); int clr[] = {x, y}; auto cost = [&] (int i, int color) { return int(clr[color] != c[i]); }; // dp[cut 01][last][parity] array<array<array<int, 2>, 2>, 2> dp; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) dp[i][j][k] = INF; dp[0][0][1] = cost(0, 0); dp[0][1][1] = cost(0, 1); for(int idx = 1; idx < n; idx++) { array<array<array<int, 2>, 2>, 2> ndp; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) ndp[i][j][k] = INF; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) { for(int l = 0; l < 2; l++) { if(j == l) cmin(ndp[i][l][k ^ 1], dp[i][j][k] + cost(idx, l)); else { if(i && k) continue; cmin(ndp[1][l][1], dp[i][j][k] + cost(idx, l)); } } } swap(dp, ndp); } int mn = INF; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) cmin(mn, dp[i][j][k]); return mn + lazy; }; for(int i = 0; i < m; i++) ans[i] = n - pos[i].size(); for(int i = 0; i < m; i++) for(int j = 0; j < i; j++) { int tt = go(i, j); ans[i] = min(ans[i], tt); ans[j] = min(ans[j], tt); } for(int i = 0; i < m; i++) cout << ans[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...