Submission #294764

#	Time	Username	Problem	Language	Result	Execution time	Memory
294764		Berted	Paint By Numbers (IOI16_paint)	C++14	100 / 100	385 ms	52804 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <vector>
#include <assert.h>
#include <iostream>
using namespace std;

string S;
int N, K, C[200001];
int pref[200001], kp[200001];
bool DP[101][200001];
bool trav[101][200001];
bool ans[200001][2];

void backtrack(int k, int n)
{
	if (!trav[k][n])
	{
		//cout << "BKTRK " << k << " " << n << "\n";
		trav[k][n] = 1;
		if (n && S[n - 1] != 'X' && DP[k][n - 1]) 
		{
			ans[n - 1][1] = 1;
			backtrack(k, n - 1);
		}
		if (k && n >= C[k - 1] + (k > 1) && pref[n] == pref[n - C[k - 1]] && ((k == 1) || S[n - C[k - 1] - 1] != 'X') && DP[k - 1][n - C[k - 1] - (k > 1)])
		{
			if (k > 1) ans[n - C[k - 1] - 1][1] = 1;
			kp[n - C[k - 1]] = max(kp[n - C[k - 1]], C[k - 1]);
			backtrack(k - 1, n - C[k - 1] - (k > 1));
		}
	}
}

string solve_puzzle(string s, vector<int> c) 
{
	N = s.size(); K = c.size();
	S = s;
	for (int i = 0; i < K; i++) {C[i] = c[i];}
	for (int i = 1; i <= N; i++) {pref[i] = pref[i - 1] + (s[i - 1] == '_');}

	DP[0][0] = 1;
	for (int j = 1; j <= N && s[j - 1] != 'X'; j++) {DP[0][j] = 1;}
	for (int i = 1; i <= K; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (s[j - 1] != 'X') DP[i][j] |= DP[i][j - 1];
			if (j >= c[i - 1] + (i > 1) && pref[j] == pref[j - c[i - 1]] && ((i == 1) || s[j - c[i - 1] - 1] != 'X'))
			{
				DP[i][j] |= DP[i - 1][j - c[i - 1] - (i > 1)];
			}
			//cout << i << " " << j << " " << DP[i][j] << "\n";
		}
	}

	assert(DP[K][N]);
	backtrack(K, N);

	int cur = 0;

	for (int i = 0; i < N; i++)
	{
		//cout << kp[i] << "\n";
		if (kp[i]) {cur = max(cur, kp[i] + i);}
		ans[i][0] = (i < cur);
	}

	string ret = "";
	for (int i = 0; i < N; i++)
	{
		if (ans[i][0] && ans[i][1]) {ret.push_back('?');}
		else if (ans[i][0]) {ret.push_back('X');}
		else {ret.push_back('_');}
	}

    return ret;
}

• 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