Submission #57840

#	Time	Username	Problem	Language	Result	Execution time	Memory
57840		robert	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2065 ms	103084 KiB

paint

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, K;
vector<int> nd; //number of blocks needed to place the last x blocks, not including the space at the beginning
int m[200100][110]; //index, number of blocks remaining
string a, s;
vector<int> c;
//index, number of blocks set, length of current block remaining, forced empty space
int solve(int n, int k, int cl, bool es){
	//cout << n << " " << k << " " << cl << " " << es << " " << endl;
	if(n==N&&cl==0&&K==k) //we reached the end, no more blocks to add
		return 1;
	else if(n==N)
		return 0;
	if(k>K)
		return 0;
	if(nd[k]+cl+es>N-n)
		return 0;
	
	if(cl==0&&!es){ //block length remaining 0 and previous index was not black
		//we can add a new one
		if(m[n][k]!=-1)
			return m[n][k];
		if(s[n]=='X') //have to start a new block
			return m[n][k] = solve(n+1, k+1, c[k]-1, 1);
		else if(s[n]=='_') //forced whitespace
			return m[n][k] = solve(n+1, k, 0, 0);
		else {
			int ret = m[n][k] = solve(n+1, k, 0, 0);
			if(ret){
				//possible with whitespace
				if(a[n]=='.')
					a[n] = '_';
				else if(a[n]!='_')
					a[n] = '?';
			}
			ret = solve(n+1, k+1, c[k]-1, 1);
			if(ret){
				//possible with black space
				if(a[n]=='.')
					a[n] = 'X';
				else if(a[n]!='X')
					a[n] = '?';
			}
			return m[n][k] = m[n][k] || ret;
		}
	}
	else if(cl==0){
		//just ended a block
		if(s[n]=='X')
			return 0; //not possible, put whitespace on black block
		int res = solve(n+1, k, 0, 0);
		if(res){ //if this spot can be white
			if(a[n]=='.')
				a[n] = '_';
			else if(a[n]!='_') //not white or unknown, and thus black or both
				a[n] = '?';
		}
		return res;
	} else {
		//in a block right now
		if(s[n]=='_') //block on whitespace
			return 0; //not possible
		else {
			int ret = solve(n+1, k, cl-1, 1);
			if(ret){
				//if we can put a block here
				if(a[n]=='.')
					a[n] = 'X';
				else if(a[n]!='X')
					a[n] = '?';
			}
			return ret;
		}
	}
}

string solve_puzzle(string m_s, vector<int> c_a){
	N = m_s.length();
	c = c_a;
	s = m_s;
	K = c_a.size();
	a = s;
	nd.assign(K+1, -1);
	for(int y=K-1; y>=0; y--){
		nd[y] = nd[y+1]+c[y]+1;
	}
	memset(m, -1, sizeof(m));
	solve(0, 0, 0, 0);
	return a;
}
/*
int main(){
	vector<int> d = {3};
	cout << solve_puzzle(".X........", d) << endl;
//	cout << m[0][0] << endl;
	return 0;
}*/

• 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: 0 / 10