Submission #1047362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047362		pawned	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2032 ms	146768 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"

string merge(string s, string t) {	// s is before t
	if (s[0] == '!')
		return t;
	int N = s.size();
	string res = "";
	for (int i = 0; i < N; i++) {
		if (s[i] == '?' || t[i] == '?')
			res += '?';
		else if (s[i] != t[i])
			res += '?';
		else
			res += s[i];
	}
	return res;
}

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<string>> dp(N, vector<string>(K + 1));
	// dp[i][j]: string with 'X', '_', '?'; full "!!!" if none possible
	// check whether completing up to kth range at pos i is possible
	for (int i = 0; i < N; i++) {
//		cout<<"at "<<i<<endl;
		if (s[i] == '_') {
			for (int j = 0; j <= K; j++) {
				dp[i][j] = string(N, '!');
			}
			continue;
		}
		dp[i][0] = "";	// base
		bool canbase = true;
		for (int j = 0; j <= i; j++) {
			if (s[j] == 'X')
				canbase = false;
		}
		if (canbase) {
			for (int j = 0; j <= i; j++) {
				if (s[j] != '?')
					dp[i][0] += s[j];
				else
					dp[i][0] += '_';
			}
		}
		else {
			dp[i][0] = string(N, '!');
		}
		for (int j = 1; j <= K; j++) {	// finished all until j - 1
			// consider previous range
			if (i + 1 < c[j - 1]) {
				dp[i][j] = string(N, '!');
				continue;
			}
			bool can = true;
			for (int k = i; k >= i - c[j - 1] + 1; k--) {	// all 'X'
				if (s[k] == '_')
					can = false;
			}
			if (!can) {
				dp[i][j] = string(N, '!');
				continue;
			}
			if (i + 1 == c[j - 1]) {	// then j = 1, must be very start
				if (j != 1) {
					dp[i][j] = string(N, '!');
				}
				else {
					dp[i][j] = string(c[j - 1], 'X');
				}
			}
			else {	// has '_' before, not start
				if (s[i - c[j - 1]] == 'X') {	// must put '_'
					dp[i][j] = string(N, '!');
				}
				else {
					// try all previous
					dp[i][j] = string(N, '!');
					for (int k = i - c[j - 1] - 1; k >= 0; k--) {
						// try with previous; prev ends at k (inclusive)
						bool canadd = true;
						for (int l = k + 1; l < i - c[j - 1] + 1; l++) {
							if (s[l] == 'X') {
								canadd = false;
								break;
							}
						}
						if (canadd) {
							if (dp[k][j - 1][0] != '!') {
								// found solution
								string t = dp[k][j - 1];
								for (int l = 0; l < i - c[j - 1] - k; l++) {
									t += '_';
								}
								for (int l = 0; l < c[j - 1]; l++) {
									t += 'X';
								}
								// merge t and the current dp[i][j]
//								cout<<"t: "<<t<<endl;
								dp[i][j] = merge(dp[i][j], t);
							}
						}
					}
					// try with nothing behind
					if (j == 1) {
						bool canadd = true;
						for (int l = 0; l < i - c[j - 1] + 1; l++) {
							if (s[l] == 'X') {
								canadd = false;
								break;
							}
						}
						if (canadd) {
							string t = "";
							for (int l = 0; l < i - c[j - 1] + 1; l++) {
								t += '_';
							}
							for (int l = 0; l < c[j - 1]; l++) {
								t += 'X';
							}
//							cout<<"last t: "<<t<<endl;
							dp[i][j] = merge(dp[i][j], t);
						}
					}
				}
			}
		}
	}
/*	cout<<"dp: "<<endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= K; j++) {
			cout<<dp[i][j]<<"; ";
		}
		cout<<endl;
	}*/
	// ans is combining all the dp's
	string ans(N, '!');
	for (int i = 0; i < N; i++) {
		if (dp[i][K][0] != '!') {
			bool can = true;
			if (dp[i][K].size() != N) {
				for (int j = (int)(dp[i][K].size()); j < N; j++) {
					if (s[j] == 'X')
						can = false;
				}
			}
			if (can) {
				string tm = dp[i][K];
				while (tm.size() < N)
					tm += '_';
				ans = merge(ans, tm);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, vi)':
paint.cpp:160:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  160 |    if (dp[i][K].size() != N) {
      |        ~~~~~~~~~~~~~~~~^~~~
paint.cpp:168:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  168 |     while (tm.size() < N)
      |            ~~~~~~~~~~^~~

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