Submission #48628

#	Time	Username	Problem	Language	Result	Execution time	Memory
48628		alenam0161	Paint By Numbers (IOI16_paint)	C++17	59 / 100	78 ms	81876 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
const int N = 2e5 + 7;
const int K = 207;
bool pre[N][K];
bool suf[N][K];
int gum[N];
int hwl[N];
int hwr[N];
int p[N];
int G[N];
int ok(int l, int r) {
	if (l > r)return -1000007;
	if (l <1)return gum[r];
	return gum[r] - gum[l - 1];
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
	for (int i = 0; i < N - 2; i++)suf[i][0] = pre[i][0] = 1;
	int k = c.size();
	int n = s.length();
	for (int i = 0; i < k; ++i)c[i];
	for (int i = 0; i < n; ++i) {
		gum[i] = s[i] != '_';
		if (i)gum[i] += gum[i - 1];
	}
	for (int i = 0; i < n; ++i) {
		if (i == 0)hwl[i] = s[i] == 'X';
		else {
			if (s[i] != s[i - 1] && s[i] == 'X')hwl[i] = 1 + hwl[i - 1];
			else hwl[i] = hwl[i - 1];
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		if (i == n - 1)hwr[i] = s[i] == 'X';
		else {
			if (s[i] != s[i + 1] && s[i] == 'X')hwr[i] = 1 + hwr[i + 1];
			else hwr[i] = hwr[i + 1];
		}
	}
	for (int i = 0; i < n; ++i) {
		int x = 0;
		for (int j = 0; j <= k; ++j) {
			if (j == 0) {
				pre[i][j] = (hwl[i] == 0)&(i == 0 || (pre[i - 1][j]));
				continue;
			}
			x += c[j - 1];
			if (i + 1 >= x) {
				if (j == 1 && ok(i - c[j - 1] + 1, i) == c[j - 1]&&(i-c[j-1]+1==0||hwl[i-c[j-1]]==0)) {
					pre[i][j] = true;
				}
				else {
					if (ok(i - c[j - 1] + 1, i) == c[j - 1] && pre[i - c[j - 1] - 1][j - 1] == true) {
						pre[i][j] = true;
					}
					else if (i > 0 && pre[i - 1][j] == true && s[i] != 'X') {
						pre[i][j] = true;
					}
				}
			}
			x++;
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		int x = 0;
		int r = k - 1;
		for (int j = 0; j <= k; ++j) {
			if (j == 0) {
				suf[i][j] = (hwr[i] == 0)&(i == n - 1 || (suf[i + 1][j]));
				continue;
			}
			x += c[r];
			if (j == 1 && ok(i, i + c[r] - 1) == c[r]&&(i+c[r]==n||hwr[i+c[r]]==0)) {
				suf[i][j] = true;
			}
			else {
				if (ok(i, i + c[r] - 1) == c[r] && suf[i + c[r] + 1][j - 1] == true) {
					suf[i][j] = true;
				}
				else if (suf[i + 1][j] == true && s[i] != 'X') {
					suf[i][j] = true;
				}
			}
			r--;
			x++;
		}
	}
	string ans = s;

	for (int i = 0; i < n; ++i) {
		if (s[i] == '.' || s[i] == 'X') {
			int O = 0;
			for (int j = 0; j < k; ++j) {
				int h = k - j - 1;
				if (ok(i, i + c[j] - 1) == c[j]) {
					if (i > 1 && pre[i - 2][j] == false)continue;
					if (i <= 1) {
						if (j != 0)continue;
					}
					if (i > 0 && s[i - 1] == 'X')continue;
					if (i+c[j]+1<n&&suf[i + c[j] + 1][h] == false)continue;
					if (i + c[j]+1 < n&&s[i + c[j]] == 'X')continue;
					if (i < n - 1 && s[i + c[j]] == 'X')continue;
					if (i + c[j] + 1 >= n) {
						if (h != 0)continue;
					}
					G[i] = max(G[i], c[j]);
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		G[i + 1] = max(G[i + 1], G[i] - 1);
		if (G[i] > 0)p[i] |= 1;
	}
	for (int i = 0; i < n; ++i) {
		if (s[i] == '.') {
			int O = 0;
			for (int j = 0; j <= k; ++j) {
				int h = k - j;
				if (i == 0) {
					if (j != 0)continue;
					if (suf[1][h] == false)continue;
				}
				else {
					if (pre[i - 1][j] == false)continue;
					if (suf[i + 1][h] == false)continue;
				}
				p[i] |= 2;
			}
			if (p[i] == 2)ans[i] = '_';
			else if (p[i] == 1)ans[i] = 'X';
			else ans[i] = '?';
			assert(p[i] >0);
		}
	}

	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:98:8: warning: unused variable 'O' [-Wunused-variable]
    int O = 0;
        ^
paint.cpp:124:8: warning: unused variable 'O' [-Wunused-variable]
    int O = 0;
        ^

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