Submission #789189

#	Time	Username	Problem	Language	Result	Execution time	Memory
789189		NothingXD	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	340 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], 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;
		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] && (j == 1 || (i > c[j-1] && dp[i-c[j-1]-1][j-1]))) 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;
		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] && (j == k || (n - i + 1 > c[j-1] && pd[i+c[j-1]+1][j+1]))) 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 ((j == 1 || (i > c[j-1] && dp[i-c[j-1]-1][j-1])) && (j == k || (j + 2 < n && pd[i+2][j+1]))){
			//	debug(i-c[j-1]+1, i, j);
				part[i-c[j-1]+1]++;
				part[i+1]--;
				trap[i+1]++;
				trap[i+2]--;
				if (j == 1){
					trap[0]++;
					trap[i-c[j-1]+1]--;
				}
				if (j == k){
					trap[i+1]++;
				}
			}
		}
	}
	ans = s;
	for (int i = 1; i <= n; i++){
		part[i] += part[i-1];
		trap[i] += trap[i-1];
		//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: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10