Submission #489167

#	Time	Username	Problem	Language	Result	Execution time	Memory
489167		cheissmart	Rope (JOI17_rope)	C++14	45 / 100	2569 ms	25700 KiB

rope

#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 %= 2;
				if(len == 0)
					len = 4;
				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';	
		
}

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20