Submission #789285

#	Time	Username	Problem	Language	Result	Execution time	Memory
789285		NothingXD	Paint By Numbers (IOI16_paint)	C++17	100 / 100	195 ms	46080 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out() {cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const int maxk = 100 + 10;
int n, k, part[maxn], trap[maxn];
bool dp[maxn][maxk], pd[maxn][maxk];
string ans;

string solve_puzzle(std::string s, std::vector<int> c) {
	n = s.size();
	k = c.size();
	int lst = 0;
	dp[0][0] = true;
	for (int i = 1; i <= n; i++){
		if (s[i-1] == '_') lst = i;
		if (dp[i-1][0] && s[i-1] != 'X') dp[i][0] = true;
		for (int j = 1; j <= k; j++){
			dp[i][j] = false;
			if (s[i-1] != 'X' && dp[i-1][j]) dp[i][j] = true;
			if (lst <= i-c[j-1] && (i == c[j-1] || s[i-c[j-1]-1] != 'X')){
				bool ok = ((i == c[j-1] && j == 1) || (i > c[j-1] && dp[i-c[j-1]-1][j-1]));
				if (ok) dp[i][j] = true;
			}
			//debug(i, j, dp[i][j]);
		}
	}
	pd[n+1][k+1] = true;
	lst = n+1;
	for (int i = n; i; i--){
		if (s[i-1] == '_') lst = i;
		if (pd[i+1][k+1] && s[i-1] != 'X') pd[i][k+1] = true;
		for (int j = 1; j <= k; j++){
			pd[i][j] = false;
			if (s[i-1] != 'X' && pd[i+1][j]) pd[i][j] = true;
			if (lst >= i+c[j-1] && (n-i+1 == c[j-1] || s[i+c[j-1]-1] != 'X')){
				bool ok = ((n-i+1 == c[j-1] && j == k) || (n-i+1 > c[j-1] && pd[i+c[j-1]+1][j+1]));
				if (ok) pd[i][j] = true;
			}
			//debug(i, j, pd[i][j]);
		}
	}
	lst = 0;
	for (int i = 1; i <= n; i++){
		if (s[i-1] == '_') lst = i;
		for (int j = 1; j <= k; j++){
			if (lst > i-c[j-1]) continue;
			if ((((i == c[j-1] && j == 1) || (i > c[j-1] && s[i-c[j-1]-1] != 'X' && dp[i-c[j-1]-1][j-1]))) && ((i == n && j == k) || (i < n && s[i] != 'X' && pd[i+2][j+1]))){
				part[i-c[j-1]+1]++;
				part[i+1]--;
			}
		}
	}
	for (int i = 1; i <= n; i++){
		if (s[i-1] == 'X') continue;
		for (int j = 0; j <= k; j++){
			//debug(i, j, dp[i-1][j], pd[i+1][j+1]);
			if (dp[i-1][j] && pd[i+1][j+1]){
			//	debug(i, j);
				trap[i]++;
			}
		}
	}
	ans = s;
	for (int i = 1; i <= n; i++){
		part[i] += part[i-1];
		if (ans[i-1] != '.') continue;
		//debug(part[i], trap[i]);
		if (part[i] && trap[i]) ans[i-1] = '?';
		else if (part[i]) ans[i-1] = 'X';
		else ans[i-1] = '_';
	}
	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