Submission #346785

#	Time	Username	Problem	Language	Result	Execution time	Memory
346785		wwdd	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1071 ms	108004 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

int ds(int pa, int pb, const string& s, vi& c, vvi& dp, vi& pr) {
	if(pa == s.size()) {
		if(pb == c.size()) {
			return 1;
		} else {
			return 0;
		}
	}
	if(dp[pa][pb] != -1) {
		return dp[pa][pb];
	}
	int res = 0;
	if(s[pa] != 'X') {
		if(ds(pa+1,pb,s,c,dp,pr) != 0) {
			res |= 1;
		}
	}
	if(pb < c.size()) {
		if(pb < c.size()-1) {
			int nx = pa+c[pb];
			if(nx+1 <= s.size()) {
				if(pr[nx]-pr[pa] == 0 && s[nx] != 'X') {
					if(ds(nx+1,pb+1,s,c,dp,pr)) {
						res |= 2;
					}
				}
			}
		} else {
			int nx = pa+c[pb];
			if(nx <= s.size()) {
				if(pr[nx]-pr[pa] == 0) {
					if(ds(nx,pb+1,s,c,dp,pr)) {
						res |= 2;
					}
				}
			}
		}
	}
	return dp[pa][pb] = res;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
	vi pr;
	pr.push_back(0);
	vvi dp;
	dp.assign(s.size()+1,vi(c.size()+1,-1));
	for(int i=0;i<s.size();i++) {
		pr.push_back(pr.back()+(s[i]=='_'));
	}
	int ru = ds(0,0,s,c,dp,pr);
	string res;
	vi wac(s.size()+1,0);
	int blu = 0;
	for(int i=0;i<s.size();i++) {
		for(int j=0;j<=c.size();j++) {
			if(dp[i][j] == -1) {continue;}
			if(dp[i][j]&1) {
				wac[i] = 1;
			}
			if(dp[i][j]&2) {
				blu = max(blu,c[j]);
				wac[i+c[j]] = 1;
			}
		}
		if(wac[i] && !blu) {
			res.push_back('_');
		} else if(blu && !wac[i]) {
			res.push_back('X');
		} else {
			res.push_back('?');
		}
		blu = max(blu-1,0);
	}
	return res;
}

Compilation message (stderr)

paint.cpp: In function 'int ds(int, int, const string&, vi&, vvi&, vi&)':
paint.cpp:10:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  if(pa == s.size()) {
      |     ~~~^~~~~~~~~~~
paint.cpp:11:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   if(pb == c.size()) {
      |      ~~~^~~~~~~~~~~
paint.cpp:26:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if(pb < c.size()) {
      |     ~~~^~~~~~~~~~
paint.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if(pb < c.size()-1) {
      |      ~~~^~~~~~~~~~~~
paint.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |    if(nx+1 <= s.size()) {
      |       ~~~~~^~~~~~~~~~~
paint.cpp:38:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    if(nx <= s.size()) {
      |       ~~~^~~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<s.size();i++) {
      |              ~^~~~~~~~~
paint.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<s.size();i++) {
      |              ~^~~~~~~~~
paint.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int j=0;j<=c.size();j++) {
      |               ~^~~~~~~~~~
paint.cpp:57:6: warning: unused variable 'ru' [-Wunused-variable]
   57 |  int ru = ds(0,0,s,c,dp,pr);
      |      ^~

• 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