Submission #294982

#	Time	Username	Problem	Language	Result	Execution time	Memory
294982		Plurm	Paint By Numbers (IOI16_paint)	C++11	100 / 100	441 ms	44212 KiB

paint

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

int qsw[200005];
int qsb[200005];
int evp[200005];
int qs[200005];
bool dp[128][200005];
bool dpb[128][200005];
bool dps[128][200005];
string solve_puzzle(string s, vector<int> c){
	int n = s.size();
	s.insert(s.begin(), '0');
	for(int i = 1; i <= n; i++){
		if(s[i] == '_') qsw[i] = qsw[i-1]+1;
		else qsw[i] = qsw[i-1];
		if(s[i] == 'X') qsb[i] = qsb[i-1]+1;
		else qsb[i] = qsb[i-1];
	}
	string out = s;
	int k = c.size();
	c.insert(c.begin(), 0);
	for(int i = 0; i <= n+1; i++){
		dp[0][i] = true;
		dpb[k+1][i] = true;
		dps[k+1][i] = true;
	}
	for(int j = 1; j <= k; j++){
		for(int i = c[j]; i <= n; i++){
			// if end of block is i,
			if(s[i] != 'X') dp[j][i] |= dp[j][i-1];
			if((i-c[j] == 0 || s[i-c[j]] != 'X') && qsw[i] - qsw[i-c[j]] == 0){
				bool clause = i-c[j] == 0 ? j == 1 : dp[j-1][i-c[j]-1];
				if(j == 1) clause &= qsb[i-c[j]] == 0;
				dp[j][i] |= clause;
			}
		}
	}
	for(int j = k; j > 0; j--){
		for(int i = n-c[j]+1; i > 0; i--){
			if(s[i] != 'X') dps[j][i] |= dps[j][i+1];
			if((i+c[j] == n+1 || s[i+c[j]] != 'X') && qsw[i+c[j]-1] - qsw[i-1] == 0){
				bool clause = i+c[j] == n+1 ? j == k : dps[j+1][i+c[j]+1];
				if(j == k) clause &= qsb[n] - qsb[i+c[j]-1] == 0;
				if(j != 1) clause &= dp[j-1][i-2] && s[i-1] != 'X';
				else clause &= qsb[i-1] == 0;
				dps[j][i] |= clause;
			}
		}
	}
	for(int j = 1; j <= k; j++){
		for(int i = c[j]; i <= n; i++){
			// if end of block is i,
			dp[j][i] = false;
			if(s[i] != 'X') dp[j][i] |= dp[j][i-1];
			if((i-c[j] == 0 || s[i-c[j]] != 'X') && qsw[i] - qsw[i-c[j]] == 0){
				bool clause = i-c[j] == 0 ? j == 1 : dp[j-1][i-c[j]-1];
				if(j == 1) clause &= qsb[i-c[j]] == 0;
				if(j != k) clause &= dps[j+1][i+2] && s[i+1] != 'X';
				else clause &= qsb[n] - qsb[i] == 0;
				dp[j][i] |= clause;
				if(clause){
					evp[i-c[j]+1]++;
					evp[i+1]--;
				}
			}
		}
	}
	for(int i = 1; i <= n; i++){
		qs[i] = qs[i-1] + evp[i];
		if(qs[i] > 0) out[i] = s[i] == '.' ? 'x' : s[i];
		else out[i] = '_';
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= k; j++){
			if(dp[j][i-1] && dps[j+1][i+1]){
				// i can be _
				if(out[i] == 'x') out[i] = '?';
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(out[i] == 'x') out[i] = 'X';
	}
	out.erase(out.begin());
	return out;
}

• 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