Submission #1189772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189772		stdfloat	Paint By Numbers (IOI16_paint)	C++20	100 / 100	283 ms	8380 KiB

paint

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

string solve_puzzle(string s, vector<int> C) {
	int n = (int)s.size(), m = (int)C.size();

	s = ' ' + s; C.insert(C.begin(), 0);

	vector<int> p1(n + 1), p2(n + 1);
	for (int i = 1; i <= n; i++) {
		p1[i] = p1[i - 1] + (s[i] == '_');
		p2[i] = p2[i - 1] + (s[i] == 'X');
	}

	vector<vector<bool>> dp1(m + 1, vector<bool>(n + 1));
	for (int i = 0; i <= n && !p2[i]; i++)
		dp1[0][i] = true;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (s[j] != 'X') dp1[i][j] = dp1[i][j - 1];
			if (s[j] != '_' && C[i] <= j && p1[j] == p1[j - C[i]] && s[j - C[i]] != 'X')
				dp1[i][j] = dp1[i][j] || C[i] == j || dp1[i - 1][j - C[i] - 1];
		}

		if (i == 1) s[0] = 'X';
	}
	s[0] = '.';

	p1 = p2 = vector<int>(n + 3);
	for (int i = n; i >= 0; i--) {
		p1[i] = (s[i] == '_') + p1[i + 1];
		p2[i] = (s[i] == 'X') + p2[i + 1];
	}
	vector<vector<bool>> dp2(m + 2, vector<bool>(n + 3));
	for (int i = n + 2; i >= 0 && !p2[i]; i--)
		dp2[m + 1][i] = true;

	s += '.';
	for (int i = m; i > 0; i--) {
		for (int j = n; j > 0; j--) {
			if (s[j] != 'X') dp2[i][j] = dp2[i][j + 1];
			if (s[j] != '_' && j + C[i] <= n + 1 && p1[j] == p1[j + C[i]] && s[j + C[i]] != 'X')
				dp2[i][j] = dp2[i][j] || dp2[i + 1][j + C[i] + 1];
		}

		if (i == m) s[n + 1] = 'X';
	}
	s.erase(--s.end());

	vector<int> p(n + 3);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j + C[i] <= n + 1; j++) {
			if (((j == 1 && i == 1) || (1 < j && dp1[i - 1][j - 2])) && s[j - 1] != 'X' && p1[j + C[i]] == p1[j] && s[j + C[i]] != 'X' && dp2[i + 1][j + C[i] + 1]) {
				p[j]++; p[j + C[i]]--;
			}
		}
	}
	for (int i = 1; i <= n; i++)
		p[i] += p[i - 1];

	string ans = s;
	for (int i = 1; i <= n; i++) {
		if (s[i] != '.') continue;

		if (!p[i]) {
			ans[i] = '_'; continue;
		}

		bool tr = false;
		for (int j = 0; j <= m && !tr; j++)
			tr = dp1[j][i - 1] && dp2[j + 1][i + 1];

		ans[i] = (tr ? '?' : 'X');
	}

	ans.erase(ans.begin());

	return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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