Submission #1050399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050399		pawned	Paint By Numbers (IOI16_paint)	C++17	100 / 100	245 ms	31604 KiB

paint

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "paint.h"

vector<vector<bool>> solve(string s, vi c) {
	int N = s.size();
	int K = c.size();
	vi pfs1(N + 1, 0);	// X's in prefix
	vi pfs2(N + 1, 0);	// _'s in prefix
	for (int i = 1; i <= N; i++) {
		pfs1[i] = pfs1[i - 1];
		pfs2[i] = pfs2[i - 1];
		if (s[i - 1] == 'X')
			pfs1[i]++;
		if (s[i - 1] == '_')
			pfs2[i]++;
	}
	vector<vector<bool>> dp(N + 1, vector<bool>(K + 1, false));
	// dp[i][j]: up to i (exclusive), do first j clues
	dp[0][0] = true;
	for (int i = 1; i <= N; i++) {	// at s[i - 1]
//		cout<<"at "<<i<<endl;
		if (s[i - 1] != '_') {	// try filled
			dp[i][0] = (dp[i][0] || 0);	// can't have nothing
			for (int j = 1; j <= K; j++) {
//				cout<<"j: "<<j<<endl;
				// check if can add (j-1)st clue
				if (j == 1) {	// no need _ to left
					int lb = i - c[j - 1];	// left index, all X
					int ub = i - 1;			// right index, all X
					if ((lb >= 0) && (pfs1[lb] - pfs1[0] == 0) && (pfs2[ub + 1] - pfs2[lb] == 0))
						dp[i][j] = (dp[i][j] || 1);
				}
				else {
					int lb = i - c[j - 1];	// left index, all X
					int ub = i - 1;			// right index, all X
					if (lb >= 1 && pfs2[ub + 1] - pfs2[lb] == 0 && s[lb - 1] != 'X')
						dp[i][j] = (dp[i][j] || dp[i - c[j - 1] - 1][j - 1]);
				}
			}
		}
		if (s[i - 1] != 'X') {	// try empty
			for (int j = 0; j <= K; j++) {
				dp[i][j] = (dp[i][j] || dp[i - 1][j]);
			}
		}
	}
	return dp;
}

string solve_puzzle(string s, vi c) {
	int N = s.size();
	int K = c.size();
	for (int i = 0; i < N; i++) {
		if (s[i] == '.')
			s[i] = '?';
	}
	// try all combinations of _ and X
	// check if each works
	vector<vector<bool>> dp1 = solve(s, c);
/*	cout<<"dp1: "<<endl;
	for (int i = 0; i <= N; i++) {
		cout<<i<<": ";
		for (int j = 0; j <= K; j++) {
			cout<<dp1[i][j]<<" ";
		}
		cout<<endl;
	}*/
	// calculate reverse dp
	string s2 = s;
	reverse(s2.begin(), s2.end());
	vi c2 = c;
	reverse(c2.begin(), c2.end());
	vector<vector<bool>> dp2 = solve(s2, c2);
	reverse(dp2.begin(), dp2.end());
/*	cout<<"dp2: "<<endl;
	for (int i = 0; i <= N; i++) {
		cout<<i<<": ";
		for (int j = 0; j <= K; j++) {
			cout<<dp2[i][j]<<" ";
		}
		cout<<endl;
	}*/
	// dp2[i][j]: on s[i, N - 1], true if last j can be done
	// check if can be blank
	vector<bool> can1(N, false);
	// can1[i] is true if s[i] can be '_'
	for (int i = 0; i < N; i++) {	// try splitting at i
		for (int j = 0; j <= K; j++) {	// this many to the left
			if (s[i] != 'X' && dp1[i][j] && dp2[i + 1][K - j])
				can1[i] = true;
		}
	}
/*	cout<<"can1: ";
	for (bool b : can1)
		cout<<b<<" ";
	cout<<endl;*/
	vi pfs1(N + 1, 0);	// X's in prefix
	vi pfs2(N + 1, 0);	// _'s in prefix
	for (int i = 1; i <= N; i++) {
		pfs1[i] = pfs1[i - 1];
		pfs2[i] = pfs2[i - 1];
		if (s[i - 1] == 'X')
			pfs1[i]++;
		if (s[i - 1] == '_')
			pfs2[i]++;
	}
	// check if can be filled
	vector<bool> can2(N, false);
	for (int i = 0; i < K; i++) {	// considering clue i
//		cout<<"at "<<i<<endl;
		for (int j = 0; j < N - c[i] + 1; j++) {	// clue starts at j
			// clue on [j, j + c[i] - 1]
			// immediate left and right must possibly be '_'
			bool works = true;
			if (j > 0 && s[j - 1] == 'X')
				works = false;
			if ((j + c[i] - 1) < N - 1 && s[j + c[i]] == 'X')
				works = false;
			// all within clue must possibly be 'X'
			if (pfs2[j + c[i]] - pfs2[j] != 0)
				works = false;
			if (!works)
				continue;
			// check for other clues to left and right
			// check for left possible
			bool canleft = false;
			if ((j == 0 && i == 0))
				canleft = true;
			else if (j >= 1 && s[j - 1] != 'X' && dp1[j - 1][i])
				canleft = true;
			bool canright = false;
			if ((j + c[i] - 1 == N - 1 && i == K - 1))
				canright = true;
			else if (j + c[i] - 1 < N - 1 && s[j + c[i]] != 'X' && dp2[j + c[i] + 1][K - 1 - i])
				canright = true;
			if (canleft && canright) {	// actually works
//				cout<<"works "<<i<<" "<<j<<endl;
				for (int k = j; k <= j + c[i] - 1; k++) {
					can2[k] = true;
				}
			}
		}
	}
/*	cout<<"can2: ";
	for (bool b : can2)
		cout<<b<<" ";
	cout<<endl;*/
	string ans = "";
	for (int i = 0; i < N; i++) {
		if (can1[i] && can2[i]) // both
			ans += '?';
		else if (can1[i])	// only empty
			ans += '_';
		else if (can2[i])	// only filled
			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