Submission #52143

#	Time	Username	Problem	Language	Result	Execution time	Memory
52143		aome	Paint By Numbers (IOI16_paint)	C++17	100 / 100	600 ms	153068 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n, m;
int sumwhite[N], sumf[N][105];
bool isblack[N], iswhite[N];
bool fpre[N][105], fsuf[N][105];
bool flag[N][105];

string solve_puzzle(string s, vector<int> c) {
   	n = s.size(), m = c.size();
   	for (int i = 1; i <= n; ++i) {
   		sumwhite[i] = sumwhite[i - 1] + (s[i - 1] == '_');
   	}
   	fpre[0][0] = fsuf[n + 1][m + 1] = 1;
   	for (int i = 1; i <= n; ++i) {
   		for (int j = 0; j <= m; ++j) {
   			if (s[i - 1] != 'X') fpre[i][j] |= fpre[i - 1][j];
   			if (j >= 1 && i >= c[j - 1] && sumwhite[i] - sumwhite[i - c[j - 1]] == 0) {
   				if (i > c[j - 1] && s[i - c[j - 1] - 1] == 'X') continue;
   				fpre[i][j] |= flag[i][j] = fpre[max(0, i - c[j - 1] - 1)][j - 1];
   			}
   		}
   	}
   	for (int i = n; i >= 1; --i) {
   		for (int j = m + 1; j >= 1; --j) {
   			if (s[i - 1] != 'X') fsuf[i][j] |= fsuf[i + 1][j];
   			if (j <= m && n - i + 1 >= c[j - 1] && sumwhite[i + c[j - 1] - 1] - sumwhite[i - 1] == 0) {
   				if (n - i + 1 > c[j - 1] && s[i + c[j - 1] - 1] == 'X') continue;
   				fsuf[i][j] |= fsuf[min(n + 1, i + c[j - 1] + 1)][j + 1];
   			}
   		}
   	}
   	for (int i = 1; i <= n; ++i) {
   		for (int j = 1; j <= m; ++j) {
   			if (i == n) {
   				sumf[i][j] = sumf[i - 1][j] + (flag[i][j] && j == m);
   			}
   			else {
   				sumf[i][j] = sumf[i - 1][j] + (flag[i][j] && s[i] != 'X' && fsuf[i + 2][j + 1]);
   			}
   		}
   	}
   	for (int i = 1; i <= n; ++i) {
   		isblack[i] = s[i - 1] == 'X';
   		iswhite[i] = s[i - 1] == '_';
   	}
   	for (int i = 1; i <= n; ++i) {
   		if (s[i - 1] != '.') continue;
   		for (int j = 0; j <= m; ++j) {
   			if (fpre[i - 1][j] && fsuf[i + 1][j + 1]) iswhite[i] = 1;
   		}
   		for (int j = 1; j <= m; ++j) {
   			if (sumf[min(n, i + c[j - 1] - 1)][j] - sumf[i - 1][j]) isblack[i] = 1;
   		}
   	}
   	string res;
   	for (int i = 1; i <= n; ++i) {
   		if (isblack[i] && iswhite[i]) res.push_back('?');
   		else if (iswhite[i]) res.push_back('_');
   		else res.push_back('X');
   	}
   	return res;
}

• 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