Submission #285107

#	Time	Username	Problem	Language	Result	Execution time	Memory
285107		user202729	Paint By Numbers (IOI16_paint)	C++17	100 / 100	267 ms	7928 KiB

paint

// moreflags=grader.cpp
#include "paint.h"
// 15
// It's weird that the wrong code can pass many subtasks.
// !?

#include <cstdlib>
#include<climits>
#if not LOCAL
#define NDEBUG 1
#endif
#include<cassert>

struct D{
	std::vector<int> nextFail; // first >=index, or INT_MAX
	D(std::string const& s, auto satisfy): nextFail(s.size()){
		int cur=INT_MAX;
		for(int i=(int)s.size(); i--;){
			if(not satisfy(s[i])) cur=i;
			nextFail[i]=cur;
		}
	}
	bool allSatisfy(int left, int right) const{
		assert(left<right);
		return nextFail[left]>=right;
	}
};
std::string solve_puzzle(std::string s, std::vector<int> c) {
	D checkx{s, [&](char ch){return ch!='_';}};

	std::vector<std::vector<bool>> matchLeft(c.size()+1, std::vector<bool>(s.size()+1));
	// [lenc][lens]
	for(int lens=0;; ++lens){
		matchLeft[0][lens]=true;
		if(lens==(int)s.size()) break;
		if(s[lens]=='X') break;
	}
	for(int lenc=1; lenc<=(int)c.size(); ++lenc){
		auto const curc=c[lenc-1];
		for(int lens=1; lens<=(int)s.size(); ++lens){
			matchLeft[lenc][lens]=(
					matchLeft[lenc][lens-1] and s[lens-1]!='X'
					) or (
						lens>=curc and checkx.allSatisfy(lens-curc, lens) and
						(lens==curc ? lenc==1: (s[lens-curc-1]!='X' and matchLeft[lenc-1][lens-curc-1]))
						);
		}
	}

	std::vector<std::vector<bool>> matchRight(c.size()+1, std::vector<bool>(s.size()+1));
	// [lenc][lens] (from the right)
	for(int lens=0;; ++lens){
		matchRight[0][lens]=true;
		if(lens==(int)s.size()) break;
		if(s.rbegin()[lens]=='X') break;
	}
	for(int lenc=1; lenc<=(int)c.size(); ++lenc){
		auto const curc=c.rbegin()[lenc-1];
		for(int lens=1; lens<=(int)s.size(); ++lens){
			matchRight[lenc][lens]=(
					matchRight[lenc][lens-1] and s.rbegin()[lens-1]!='X'
					) or (
						lens>=curc and checkx.allSatisfy((int)s.size()-lens, (int)s.size()-lens+curc) and
						(lens==curc ? lenc==1: (s.rbegin()[lens-curc-1]!='X' and matchRight[lenc-1][lens-curc-1]))
						);
		}
	}

	std::string result(s.size(), 0);
	char const crossable=1, blankable=2;

	for(int index=0; index<(int)s.size(); ++index){
		for(int lenc=0; lenc<=(int)c.size(); ++lenc){
			if(s[index]=='_' // assumes that there always exists a solution
					or (
						s[index]=='.' and
						matchLeft[lenc][index] and matchRight[c.size()-lenc][(int)s.size()-index-1]
			  )){
				result[index]|=blankable;
				break;
			}
		}
	}

	std::vector<int> fillTemp(s.size());
	auto const fillx=[&](int left, int right){
		assert(left<right);
		fillTemp[left]=std::max(fillTemp[left], right);
	};
	for(int indexc=0; indexc<(int)c.size(); ++indexc){
		auto const curc=c[indexc];
		for(int index=curc; index<=(int)s.size(); ++index)
			if(
					(index==(int)s.size() ? indexc==(int)c.size()-1 : (
											  matchRight[c.size()-1-indexc][s.size()-index-1] and
											  s[index]!='X')) and
					(index-curc==0 ? indexc==0 : (
									   matchLeft[indexc][index-curc-1] and
									   s[index-curc-1]!='X')) and
					checkx.allSatisfy(index-curc, index)
					){
				//result[index]|=blankable;
				//result[index-curc-1]|=blankable;
				fillx(index-curc, index);
			}
	}

	for(int index=0; index<(int)s.size(); ++index){
		if(fillTemp[index]>index){
			result[index]|=crossable;
			if(index==(int)s.size()-1) break;
			fillTemp[index+1]=std::max(fillTemp[index+1], fillTemp[index]);
		}
	}

	for(auto& it: result){
		assert(it<=(crossable|blankable));
		auto const pattern="#X_?";
		assert(pattern[int(crossable)]=='X');
		assert(pattern[int(blankable)]=='_');
		assert(pattern[int(crossable|blankable)]=='?');
		it=pattern[int(it)];
	}

	return result;
}

Compilation message (stderr)

paint.cpp:16:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   16 |  D(std::string const& s, auto satisfy): nextFail(s.size()){
      |                          ^~~~

• 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