Submission #393860

#	Time	Username	Problem	Language	Result	Execution time	Memory
393860		JimmyZJX	Paint By Numbers (IOI16_paint)	C++14	10 / 100	2092 ms	98308 KiB

paint

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
typedef vector<vector<vector<int>>> Viii;
typedef vector<vector<pair<int, int>>> Vip;

#define forR(i, n) for (int i = 0; i < (n); i++)

int dp[5003][5003];

bool has_solution(const string& _s, const Vi& c) {
	int k = c.size();
	int n = _s.size();

	string s = "_" + _s;

	memset(dp, 0, sizeof(dp));
	// [i][j] : s[1 .. i] matches c[0 .. j-1]

	forR(i, n + 1) {
		if (s[i] == 'X')
			break;
		else
			dp[i][0] = 1;
	}

	int lastWhite = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i] == '_') lastWhite = i;
		int potentialBlack = i - lastWhite;
		for (int j = 1; j <= k; j++) {
			if (potentialBlack >= c[j - 1] && s[i - c[j - 1]] != 'X'
				&& (i + 1 > n || s[i + 1] != 'X')) {
				// can choose c[j-1]
				if (i - c[j - 1] - 1 < 0) {
					dp[i][j] = j == 1;
				} else if (dp[i - c[j - 1] - 1][j - 1]) {
					dp[i][j] = 1;
				}
			}
			if (s[i] != 'X') {
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			}
		}
	}

	return dp[n][k];
}

string solve_puzzle(string s, Vi c) {
	int n = s.size();
	string s_ans = s;
	for (int i = 0; i < n; i++) {
		if (s[i] == '.') {
			// try white
			s[i] = '_';
			bool white = has_solution(s, c);
			// try black
			s[i] = 'X';
			bool black = has_solution(s, c);
			s[i] = '.';

			if (black && white) {
				s_ans[i] = '?';
			} else if (white) {
				s_ans[i] = '_';
			} else {
				assert(black);
				s_ans[i] = 'X';
			}
		}
	}
	return s_ans;
}

#ifdef TEST_LOCAL
int main() {
	auto r = solve_puzzle(".................", Vi{ 2,3,6,2 });

	return 0;
}
#endif

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10