Submission #405914

#	Time	Username	Problem	Language	Result	Execution time	Memory
405914		Kevin_Zhang_TW	Paint By Numbers (IOI16_paint)	C++17	100 / 100	570 ms	209900 KiB

paint

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

#include "paint.h"

const int MAX_N = 200010, MAX_K = 105;

bool dp1[MAX_N][MAX_K], dp2[MAX_N][MAX_K];
int from1[MAX_N][MAX_K], from2[MAX_N][MAX_K];
char w[MAX_N];
int pf0[MAX_N], pf1[MAX_N], n;
int be0[MAX_N], be1[MAX_N];
int len[MAX_K], m;

int cnt1(int l, int r) { return pf1[r] - pf1[l-1]; }
int cnt0(int l, int r) { return pf0[r] - pf0[l-1]; }

void makedp1() {
	for (int i = len[1];i <= n;++i) 
		dp1[i][1] = cnt0(i-len[1]+1, i) == 0 && cnt1(1, i-len[1]) == 0;
	
	vector<int> f(m + 1);
	for (int i = 1;i <= n;++i) {
		for (int j = 2;j <= m;++j) {
			if (len[j] > i || w[i-len[j]] == 'X' || cnt0(i-len[j]+1, i)) continue;
			int &k = f[j];
			while (k < i - len[j] &&
					(!dp1[k][j-1] || cnt1(k+1, i-len[j]))) ++k;
			if (k < i - len[j]) {
				assert(dp1[k][j-1] && cnt1(k+1, i-len[j]) == 0);
				dp1[i][j] = true;
				from1[i][j] = k;
			}
		}
	}
}
void makedp2() {
	for (int i = 1;i <= n - len[m] + 1;++i) {
		dp2[i][m] = cnt0(i, i+len[m]-1) == 0 && cnt1(i+len[m], n) == 0;
		from2[i][m] = n + 1;
	}

	vector<int> f(m + 1, n);
	for (int i = n;i >= 1;--i) {
		for (int j = 1;j < m;++j) {
			if (i + len[j] - 1 > n || w[i+len[j]] == 'X' || cnt0(i, i+len[j]-1)) continue;
			int &k = f[j];
			while (k > i + len[j] &&
					(!dp2[k][j+1] || cnt1(i+len[j], k-1))) --k;
			if (k > i + len[j]) {
				assert(dp2[k][j+1] && cnt1(i+len[j], k-1) == 0);
				dp2[i][j] = true;
				from2[i][j] = k;
			}
		}
	}
}

void collect() {
	for (int i = 1;i <= n;++i) {
		for (int j = 1;j <= m;++j) {
			if (dp1[i][j] && dp2[i - len[j] + 1][j]) {
				int l = i - len[j] + 1, r = i;
				++be0[ from1[i][j] + 1 ];
				--be0[ l ];

				++be1[ l ];
				--be1[ r+1 ];

				++be0[ r+1 ];
				--be0[ from2[i - len[j] + 1][j] ];
			}
		}
	}
	for (int i = 1;i <= n;++i) {
		be1[i] += be1[i-1];
		be0[i] += be0[i-1];
	}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
	static int cnt;
	assert(++cnt == 1);
	n = s.size();
	for (int i = 1;i <= n;++i) {
		pf0[i] = pf0[i-1] + (s[i-1] == '_');
		pf1[i] = pf1[i-1] + (s[i-1] == 'X');
		w[i] = s[i-1];
	}
	m = c.size();
	for (int i = 1;i <= m;++i)
		len[i] = c[i-1];

	makedp1();
	makedp2();
	collect();

	string res(n, '?');

	for (int i = 1;i <= n;++i) {
		assert(be0[i] || be1[i]);
		if (be0[i] && be1[i]) continue;

		if (be0[i])
			res[i-1] = '_';
		if (be1[i])
			res[i-1] = 'X';
	}

	for (int i = 0;i < n;++i) {
		if (s[i] != '.' && res[i] != '?') assert(res[i] == s[i]);
	}

	return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10