Submission #538040

#	Time	Username	Problem	Language	Result	Execution time	Memory
538040		pavement	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1501 ms	35156 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;

typedef pair<int, int> ii;
#define mp make_pair

int W[200005], B[200005], cov[200005];
bitset<200005> cb, cw;
bitset<105> rdy[200005], mem[200005], rdy2[200005], mem2[200005];
vector<int> c;
string s;

bool dp(int n, int k) {
	if (n <= -1) return k == -1;
	if (k == -1) return B[n] == 0;
	if (rdy[n][k]) return mem[n][k];
	bool ret = 0;
	if (s[n] != 'X') ret |= dp(n - 1, k);
	if (k == 0 && n + 1 >= c[k] && W[n] - (n - c[k] < 0 ? 0 : W[n - c[k]]) == 0 && (n - c[k] >= 0 ? !B[n - c[k]] : 1)) ret |= 1;
	else if (k && n + 1 >= c[k] && W[n] - (n - c[k] < 0 ? 0 : W[n - c[k]]) == 0 && (n - c[k] >= 0 ? s[n - c[k]] != 'X' : 1)) ret |= dp(n - c[k] - 1, k - 1);
	rdy[n][k] = 1;
	return mem[n][k] = ret;
}

bool dp2(int n, int k) {
	if (n >= s.size()) return k == c.size();
	if (k == c.size()) return B[s.size() - 1] - (n == 0 ? 0 : B[n - 1]) == 0;
	if (rdy2[n][k]) return mem2[n][k];
	bool ret = 0;
	if (s[n] != 'X') ret |= dp2(n + 1, k);
	if (k == c.size() - 1 && n + c[k] - 1 < s.size() && W[n + c[k] - 1] - (n == 0 ? 0 : W[n - 1]) == 0 && B[s.size() - 1] - B[n + c[k] - 1] == 0) ret |= 1;
	else if (k != c.size() - 1 && n + c[k] - 1 < s.size() && W[n + c[k] - 1] - (n == 0 ? 0 : W[n - 1]) == 0 && (n + c[k] < s.size() ? s[n + c[k]] != 'X' : 1)) ret |= dp2(n + c[k] + 1, k + 1);
	rdy2[n][k] = 1;
	return mem2[n][k] = ret;
}

string solve_puzzle(string s, vector<int> c) {
	::s = s;
	::c = c;
	for (int i = 0; i < s.size(); i++) {
		if (i) W[i] = W[i - 1];
		if (i) B[i] = B[i - 1];
		W[i] += (s[i] == '_');
		B[i] += (s[i] == 'X');
	}
	string ret = s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != '.') continue;
		for (int j = -1; j < (int)c.size(); j++)
			if (dp(i - 1, j) && dp2(i + 1, j + 1)) cw[i] = 1;
	}
	for (int i = 0; i < c.size(); i++)
		for (int j = 0; j < s.size() - c[i] + 1; j++) {
			bool tmp = 0;
			if (W[j + c[i] - 1] - (j == 0 ? 0 : W[j - 1]) == 0 && (i && j ? s[j - 1] != 'X' : 1) && (i != c.size() - 1 && j != s.size() - 1 ? s[j + c[i]] != 'X' : 1)) {
				tmp = 1;
				if (i && !dp(j - 2, i - 1)) tmp = 0;
				if (i != c.size() - 1 && !dp2(j + c[i] + 1, i + 1)) tmp = 0;
			}
			if (i == 0 && j > 0 && B[j - 1]) tmp = 0;
			if (i == c.size() - 1 && B[s.size() - 1] - B[j + c[i] - 1]) tmp = 0;
			if (tmp) {
				cov[j]++;
				cov[j + c[i]]--;
			}
		}
	for (int i = 0, tot = 0; i < s.size(); i++) {
		tot += cov[i];
		if (tot) cb[i] = 1;
	}
	for (int i = 0; i < s.size(); i++) {
		if (ret[i] != '.') continue;
		if (cw[i] && cb[i]) ret[i] = '?';
		else if (cw[i]) ret[i] = '_';
		else {
			assert(cb[i]);
			ret[i] = 'X';
		}
	}
	return ret;
}

Compilation message (stderr)

paint.cpp:3: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
paint.cpp: In function 'bool dp2(int, int)':
paint.cpp:31:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  if (n >= s.size()) return k == c.size();
      |      ~~^~~~~~~~~~~
paint.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  if (n >= s.size()) return k == c.size();
      |                            ~~^~~~~~~~~~~
paint.cpp:32:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  if (k == c.size()) return B[s.size() - 1] - (n == 0 ? 0 : B[n - 1]) == 0;
      |      ~~^~~~~~~~~~~
paint.cpp:36:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  if (k == c.size() - 1 && n + c[k] - 1 < s.size() && W[n + c[k] - 1] - (n == 0 ? 0 : W[n - 1]) == 0 && B[s.size() - 1] - B[n + c[k] - 1] == 0) ret |= 1;
      |      ~~^~~~~~~~~~~~~~~
paint.cpp:36:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  if (k == c.size() - 1 && n + c[k] - 1 < s.size() && W[n + c[k] - 1] - (n == 0 ? 0 : W[n - 1]) == 0 && B[s.size() - 1] - B[n + c[k] - 1] == 0) ret |= 1;
      |                           ~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp:37:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  else if (k != c.size() - 1 && n + c[k] - 1 < s.size() && W[n + c[k] - 1] - (n == 0 ? 0 : W[n - 1]) == 0 && (n + c[k] < s.size() ? s[n + c[k]] != 'X' : 1)) ret |= dp2(n + c[k] + 1, k + 1);
      |           ~~^~~~~~~~~~~~~~~
paint.cpp:37:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  else if (k != c.size() - 1 && n + c[k] - 1 < s.size() && W[n + c[k] - 1] - (n == 0 ? 0 : W[n - 1]) == 0 && (n + c[k] < s.size() ? s[n + c[k]] != 'X' : 1)) ret |= dp2(n + c[k] + 1, k + 1);
      |                                ~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp:37:119: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  else if (k != c.size() - 1 && n + c[k] - 1 < s.size() && W[n + c[k] - 1] - (n == 0 ? 0 : W[n - 1]) == 0 && (n + c[k] < s.size() ? s[n + c[k]] != 'X' : 1)) ret |= dp2(n + c[k] + 1, k + 1);
      |                                                                                                              ~~~~~~~~~^~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
paint.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
paint.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < c.size(); i++)
      |                  ~~^~~~~~~~~~
paint.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int j = 0; j < s.size() - c[i] + 1; j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
paint.cpp:60:95: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    if (W[j + c[i] - 1] - (j == 0 ? 0 : W[j - 1]) == 0 && (i && j ? s[j - 1] != 'X' : 1) && (i != c.size() - 1 && j != s.size() - 1 ? s[j + c[i]] != 'X' : 1)) {
      |                                                                                             ~~^~~~~~~~~~~~~~~
paint.cpp:60:116: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    if (W[j + c[i] - 1] - (j == 0 ? 0 : W[j - 1]) == 0 && (i && j ? s[j - 1] != 'X' : 1) && (i != c.size() - 1 && j != s.size() - 1 ? s[j + c[i]] != 'X' : 1)) {
      |                                                                                                                  ~~^~~~~~~~~~~~~~~
paint.cpp:63:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (i != c.size() - 1 && !dp2(j + c[i] + 1, i + 1)) tmp = 0;
      |         ~~^~~~~~~~~~~~~~~
paint.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    if (i == c.size() - 1 && B[s.size() - 1] - B[j + c[i] - 1]) tmp = 0;
      |        ~~^~~~~~~~~~~~~~~
paint.cpp:72:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0, tot = 0; i < s.size(); i++) {
      |                           ~~^~~~~~~~~~
paint.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~

• 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