| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 489164 |
2021-11-21T10:51:39 Z |
cheissmart |
Rope (JOI17_rope) |
C++14 |
|
12 ms |
23756 KB |
#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] = INF;
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 time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23740 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
23756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23740 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
23756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23740 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
23756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23740 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
23756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23740 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
23756 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
