Submission #1021830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021830		vjudge1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	263 ms	48848 KiB

paint

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100;
const int maxl = 1e1 + 100;

int n, k;
bool dp[maxn][maxl];
bool d[maxn][maxl];
int a[maxn];
int b[maxn];
int c[maxn];
string s;
int w[maxn];
int bl[maxn];

bool ok(int l, int r, int c){
	if(r > n || l < 1) return 0;
	if(c){
		if(b[r] > b[l-1]) return 0;
		return 1;
	} else{
		if(a[r] > a[l-1]) return 0;
		return 1;
	}
}
string solve_puzzle(std::string S, std::vector<int> C){
	s = S;
	n = s.size();
	s = "#" + s; k = C.size();
	for(int i = 1; i <= k; i++){
		c[i] = C[i-1];
	}
	for(int i = 1; i <= n; i++){
		a[i] = a[i-1]; b[i] = b[i-1];
		if(s[i] == 'X') a[i]++;
		if(s[i] == '_') b[i]++;
	}
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= k; j++){
			if(ok(i, i, 0) && dp[i-1][j]){
				dp[i][j] = 1;
			}
			if(j){
				int l = i - c[j] - 1;
				if(j == 1) l++;
				if(l >= 0 && dp[l][j-1] && ok(i - c[j] + 1, i, 1) && (j == 1 || ok(l+1, l+1, 0))){
					dp[i][j] = 1;
				}
			}
		}
	}
	d[n+1][k+1] = 1;
	for(int i = n; i > 0; i--){
		for(int j = k + 1; j > 0; j--){
			if(ok(i, i, 0) && d[i+1][j]){
				d[i][j] = 1;
			}
			if(j <= k){
				int r = i + c[j] + 1;
				if(j == k) r--;
				if(r <= n + 1 && d[r][j+1] && ok(i, i + c[j] - 1, 1) && (j == k || ok(r-1, r-1, 0))){
					d[i][j] = 1;
				}
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(ok(i, i, 0)){
			for(int j = 0; j <= k; j++){
				if(dp[i-1][j] && d[i+1][j+1]){
					w[i] = 1;
				}
			}
		}
		for(int j = 1; j <= k; j++){
			if(ok(i, i + c[j] - 1, 1)){
				int l = i - 2;
				int r = i + c[j] + 1;
				if(j == 1) l++;
				else if(!ok(i-1, i-1, 0)) continue;
				if(j == k) r--;
				else if(!ok(i+c[j], i+c[j], 0)) continue;
				if(dp[l][j-1] && d[r][j+1]){
					bl[i]++; bl[i + c[j]]--;
				}
			}
		}
	}
	string res;
	vector<int> ans = {'.', '_', 'X', '?'};
	for(int i = 1; i <= n; i++){
		bl[i] += bl[i-1];
		int x = w[i];
		if(bl[i]) x |= 2;
		res.push_back(ans[x]);
	}
	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