Submission #285673

#	Time	Username	Problem	Language	Result	Execution time	Memory
285673		eohomegrownapps	Paint By Numbers (IOI16_paint)	C++14	100 / 100	287 ms	9096 KiB

paint

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

vector<int> blocklengths;
string requirements;

vector<int> prefsumw;
vector<int> prefsumb;

vector<vector<bool>> dpl;
//[numblocks][ind] -- ending on white
//1-indexed!
vector<vector<bool>> dpr; 
//0-indexed

int n,m;

// check whether block within a and b: prefsumw[b+1]-prefsum[a]==0
bool canFill(int a, int b){
	return prefsumw[b+1]-prefsumw[a]==0;
}
bool canEmpty(int a, int b){
	return prefsumb[b+1]-prefsumb[a]==0;
}

inline bool getL(int a, int x){
	return dpl[a][x+1];
}
inline bool getR(int a, int x){
	return dpr[a][x];
}

void gendata(){
	n = requirements.size();
	m = blocklengths.size();
	//generate prefix sums
	prefsumw.resize(n+1);
	prefsumb.resize(n+1);
	for (int i = 1; i<=n; i++){
		prefsumw[i]=prefsumw[i-1]+(requirements[i-1]=='_');
		prefsumb[i]=prefsumb[i-1]+(requirements[i-1]=='X');
	}
	//generate DP
	dpl.resize(m+1,vector<bool>(n+1,false));
	dpl[0][0]=true;
	for (int a = 0; a<=m; a++){
		for (int x = 1; x<=n; x++){
			if (requirements[x-1]=='X'){
				dpl[a][x]=false;
				continue;
			}
			if (dpl[a][x-1]){
				dpl[a][x]=true;
				continue;
			}
			if (x-2>=0&&requirements[x-2]=='W'){
				continue;
			}
			if (a>0&&x-1-blocklengths[a-1]>=0&&canFill(x-blocklengths[a-1]-1,x-2)){
				if (dpl[a-1][x-1-blocklengths[a-1]]){
					dpl[a][x]=true;
					continue;
				}
			}
		}
	}
	dpr.resize(m+1,vector<bool>(n+1,false));
	dpr[0][n]=true;
	for (int a = 0; a<=m; a++){
		for (int x = n-1; x>=0; x--){
			if (requirements[x]=='X'){
				dpr[a][x]=false;
				continue;
			}
			if (dpr[a][x+1]){
				dpr[a][x]=true;
				continue;
			}
			if (x+1<n&&requirements[x+1]=='W'){
				continue;
			}
			if (a>0&&x+1+blocklengths[m-a]<=n&&canFill(x+1,x+blocklengths[m-a])){
				if (dpr[a-1][x+1+blocklengths[m-a]]){
					dpr[a][x]=true;
					continue;
				}
			}
		}
	}
	/*for (int a = 0; a<=m; a++){
		cout<<a<<" blocks to left:\n";
		for (int i = 0; i<n; i++){
			cout<<getL(a,i)<<' ';
		}cout<<'\n';
	}
	for (int a = 0; a<=m; a++){
		cout<<a<<" blocks to right:\n";
		for (int i = 0; i<n; i++){
			cout<<getR(a,i)<<' ';
		}cout<<'\n';
	}*/
}


std::string solve_puzzle(std::string s, std::vector<int> c) {
	requirements = s;
	blocklengths = c;
	gendata();
	vector<int> canUseBlack(n+1,0);
	// what if a = 0
	for (int a = 0; a<m; a++){
		for (int x = 0; x+blocklengths[a]<=n; x++){
			//can we place block a at x?
			// possible off by one
			if (getL(a,x-1)&&getR(m-1-a,x+blocklengths[a])&&canFill(x,x+blocklengths[a]-1)){
				canUseBlack[x]++;
				canUseBlack[x+blocklengths[a]]--;
				//cout<<"can have block "<<a<<" from "<<x<<" to "<<x+blocklengths[a]-1<<'\n';
			}
		}
	}
	for (int i = 1; i<=n; i++){
		canUseBlack[i]+=canUseBlack[i-1];
	}
	/*cout<<"can have black:\n";
	for (int i = 0; i<n; i++){
		cout<<bool(canUseBlack[i]>0)<<' ';
	}cout<<'\n';*/
	vector<bool> canUseWhite(n,false);
	for (int a = 0; a<=m; a++){
		for (int x = 0; x<n; x++){
			if (getL(a,x)&&getR(m-a,x)){
				//cout<<"can have white with "<<a<<" on left at "<<x<<'\n';
				canUseWhite[x]=true;
			}
		}
	}
	/*cout<<"can have white:\n";
	for (int i = 0; i<n; i++){
		cout<<canUseWhite[i]<<' ';
	}cout<<'\n';*/

	string answer;
	for (int i = 0; i<n; i++){
		if (canUseBlack[i]>0&&canUseWhite[i]){
			answer+='?';
		} else if (canUseBlack[i]>0){
			answer+='X';
		} else if (canUseWhite[i]){
			answer+='_';
		} else {
			assert(1==0);
		}
	} 
    return answer;
}

• 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