Submission #388900

#	Time	Username	Problem	Language	Result	Execution time	Memory
388900		aarr	Paint By Numbers (IOI16_paint)	C++14	100 / 100	415 ms	126404 KiB

paint

#include "paint.h"

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

const int N = 200 * 1000 + 5, K = 105;

bool dp[N][K][3];
//vector <pair <int, pair <int, int> > > adj[N][K][3];
bool mark[N][K][3];
int e[N];
bool ans1[N];
int lt[N];

/*void dfs(int x, int y, int z) {
	if (mark[x][y][z]) {
		return;
	}
	mark[x][y][z] = true;
	for (auto p : adj[x][y][z]) {
		dfs(p.first, p.second.first, p.second.second);
	}
}*/

std::string solve_puzzle(std::string s, std::vector<int> c) {
	string ans = "";
	int n = s.size(), k = c.size();
	dp[0][0][0] = true;
	lt[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			if (s[i - 1] != 'X') {
				if (dp[i - 1][j][0]) {
					dp[i][j][0] = true;
				//	adj[i][j][0].push_back({i - 1, {j, 0}});
				}
				if (dp[i - 1][j][1]) {
					dp[i][j][0] = true;
				//	adj[i][j][0].push_back({i - 1, {j, 1}});
				}
			}
			
			if (j && s[i - 1] != '_') {
				int x = c[j - 1];
				if (dp[i - x][j - 1][0] && lt[i - 1] <= i - x) {
					dp[i][j][1] = true;
				//	adj[i][j][1].push_back({i - x, {j - 1, 0}});
				}
			}
			lt[i] = lt[i - 1];
			if (s[i - 1] == '_') {
				lt[i] = i;
			}
		}
	}
	if (dp[n][k][0]) {
		mark[n][k][0] = true;
	}
	if (dp[n][k][1]) {
		mark[n][k][1] = true;
	}
	for (int i = n; i; i--) {
		for (int j = 0; j <= k; j++) {
			if (mark[i][j][0]) {
				if (dp[i - 1][j][0]) {
					mark[i - 1][j][0] = true;
				//	adj[i][j][0].push_back({i - 1, {j, 0}});
				}
				if (dp[i - 1][j][1]) {
					mark[i - 1][j][1] = true;
				//	adj[i][j][0].push_back({i - 1, {j, 1}});
				}
			}
			
			if (mark[i][j][1]) {
				int x = c[j - 1];
				if (dp[i - x][j - 1][0] && lt[i - 1] <= i - x) {
					mark[i - x][j - 1][0] = true;
				//	adj[i][j][1].push_back({i - x, {j - 1, 0}});
				}
			}
		}
	}
	int cnt = 0;
	for (int i = n; i > 0; i--) {
		cnt -= e[i];
		for (int j = 1; j <= k; j++) {
			if (mark[i][j][1]) {
				cnt++;
				e[i - c[j - 1]]++;
			}
		}
	//	cout << "72 " << i << " " << cnt << endl;
		if (cnt > 0) {
			ans1[i] = true;
		}
	}
	for (int i = 1; i <= n; i++) {
		bool b = false;
		for (int j = 0; j <= k; j++) {
			if (mark[i][j][0]) {
				b = true;
			}
		}
		if (b) {
			if (ans1[i]) {
				ans += '?';
			}
			else {
				ans += '_';
			}
		}
		else {
			ans += 'X';
		}
	}
	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