Submission #412521

#	Time	Username	Problem	Language	Result	Execution time	Memory
412521		SeDunion	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1830 ms	262744 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
 
using DP = vector<vector<int>>;
 
template<typename T> T rev(T v) {
	reverse(v.begin(), v.end());
	return v;
}
 
DP compute_dp(string s, vector<int> c) {
	int n = s.size(), k = c.size();
	DP dp(n, vector<int>(k, 0));
	vector<int>emp(n, 1);
	for (int i = 0 ; i < n ; ++ i) {
		if (s[i] == 'X') emp[i] = 0;
		if (i > 0) emp[i] &= emp[i - 1];
	}
	for (int j = 0 ; j < k ; ++ j) {
		int last_ = -1;
		for (int i = 0 ; i < n ; ++ i) {
			if (s[i] == '_') last_ = i;
			if (last_ < i - c[j] + 1 && s[i - c[j]] != 'X') {
				dp[i][j] |= (!j && i - c[j] + 1 >= 0 && (i-c[j]<0||emp[i-c[j]]) ? 1 : (j && i - c[j] - 1 >= 0 ? dp[i - c[j] - 1][j - 1] : 0));
			}
			if (s[i] != 'X' && i > 0) {
				dp[i][j] |= dp[i - 1][j];
			}
		}
	}
	return dp;
}
 
 
string solve_puzzle(string s, vector<int> c) {
	auto dpref = compute_dp(s, c);
	auto dsuff = rev(compute_dp(rev(s), rev(c)));
	int n = s.size(), k = c.size();
	vector<int>emp(n, 1);
	vector<int>ems(n, 1);
	for (int i = 0 ; i < n ; ++ i) {
		if (s[i] == 'X') emp[i] = 0;
		if (i > 0) emp[i] &= emp[i - 1];
	}
	for (int i = n - 1 ; i >= 0 ; -- i) {
		if (s[i] == 'X') ems[i] = 0;
		if (i + 1 < n) ems[i] &= ems[i + 1];
	}
	DP can(n, vector<int>(k));
	for (int y = 0 ; y < k ; ++ y) {
		int last_ = n;
		for (int x = n - 1 ; x >= 0 ; -- x) {
			if (s[x] == '_') last_ = x;
			if (x + c[y] - 1 >= last_) {
				can[x][y] = 0;
				continue;
			}
			if (k == 1) {
				can[x][y] = ((!x || emp[x - 1]) && (x + c[y] >= n || ems[x + c[y]]));
				continue;
			}
			if (y == 0) can[x][y] = x + c[y] + 1 < n && s[x + c[y]] != 'X' && (!x || emp[x-1]) ? dsuff[x + c[y] + 1][k - 2 - y] : 0;
			else if (y == k - 1) can[x][y] = x > 1 && s[x-1] != 'X' && (x+c[y]>=n||ems[x+c[y]]) ? dpref[x - 2][y - 1] : 0;
			else can[x][y] = (x > 1 && x + c[y] + 1 < n && s[x-1] != 'X' && s[x+c[y]] != 'X') ? (dpref[x - 2][y - 1] & dsuff[x + c[y] + 1][k - 2 - y]) : 0;
		}
	}
	vector<int>canx(n), can_(n);
	for (int x = 0 ; x < n ; ++ x) {
		if (s[x] != '.') continue;
		for (int y = -1 ; y < k ; ++ y) {
			if (y == -1) can_[x] |= (x + 1 < n && k - 1 >= 0 && (!x||emp[x-1]) && dsuff[x + 1][k - 1]);
			else if (y == k - 1) can_[x] |= (x > 0 && (x+1>=n||ems[x+1]) && dpref[x - 1][y]);
			else can_[x] |= (x > 0 && x + 1 < n && dpref[x - 1][y] && dsuff[x + 1][k - y - 2]);
		}
	}
	for (int y = 0 ; y < k ; ++ y) {
		int sum = 0;
		for (int x = 0 ; x < n ; ++ x) {
			if (x - c[y] >= 0) sum -= can[x - c[y]][y];
			sum += can[x][y];
			canx[x] |= (sum > 0 ? 1 : 0);
		}
	}
	string ans = s;
	for (int i = 0 ; i < n ; ++ i) {
		if (s[i] == '.') {
			ans[i] = (canx[i] && can_[i]) ? '?' : (canx[i] ? 'X' : '_');
		} 
	}
	return ans;
}

• 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