Submission #125486

#	Time	Username	Problem	Language	Result	Execution time	Memory
125486		streifi	Paint By Numbers (IOI16_paint)	C++14	100 / 100	829 ms	108320 KiB

paint

#include "paint.h"

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

int N, K;
string s;
vector<int> c;
vector<bool> black, white;
vector<int> prefblack, prefwhite;
vector<vector<int>> memo;

bool dp(int i, int k) {
	if (i > N+1)
		return 0;
	if (memo[i][k] != -1)
		return memo[i][k];
	if (i == N+1)
		return k == K;
	bool one = s[i] != 'X' && dp(i+1, k);
	if (one)
		white[i] = true;
	bool two = false;
	if (k < K && i+c[k]+1 <= N+1) {
		two = s[i] != 'X' && s[i+c[k]+1] != 'X' && prefwhite[i+c[k]+1] == prefwhite[i+1] && dp(i+c[k]+1, k+1);
	}
	if (two) {
		/*if (memo[i+1][k] == 2) {
			black[i+1] = true;
			white[i] = true;
		} else {*/
			white[i] = white[i+c[k]+1] = true;
			for (int j = i+1; j <= i+c[k]; ++j)
				black[j] = true;
			//}
	}
	memo[i][k] = one || two;
	//cout << i << " " << k << " " << one << " " << two << endl;
	return memo[i][k];
}

string solve_puzzle(string _s, vector<int> _c) {
    s = string("_")+_s, c = _c;
	N = s.size()-1;
	K = c.size();
	black.assign(N+5, 0), white.assign(N+5, 0);
	prefblack.assign(N+5, 0), prefwhite.assign(N+5, 0);
	memo.assign(N+5, vector<int>(K+5, -1));
	
	for (int i = 0; i <= N; ++i) {
		prefblack[i+1] = prefblack[i]+(s[i]=='X');
		//cout << i << endl;
		//cout << prefwhite[i+1] << endl;
		//cout << prefwhite[i] << endl;
		//cout << s[i] << endl;
		prefwhite[i+1] = prefwhite[i]+(s[i]=='_');
	}
	for (int i = 0; i < 5; ++i) {
		prefblack.push_back(prefblack.back());
		prefwhite.push_back(prefwhite.back());
	}
	
	string ans;
	if (!dp(0, 0))
		cout << "not good" << endl;
	
	for (int i = 1; i <= N; ++i) {
		if (black[i] && white[i])
			ans.push_back('?');
		else if (black[i])
			ans.push_back('X');
		else if (white[i])
			ans.push_back('_');
		else
			cout << "shouldn\'t have happened";
	}
	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