Submission #206567

#	Time	Username	Problem	Language	Result	Execution time	Memory
206567		TAISA_	Paint By Numbers (IOI16_paint)	C++14	80 / 100	2080 ms	776 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
	int k=c.size(),n=s.size();
	auto check=[&]{
		vector<int> s0(n+1),s1(n+1);
		for(int i=0;i<n;i++){
			s0[i+1]=s0[i]+(s[i]=='_');
			s1[i+1]=s1[i]+(s[i]=='X');
		}
		vector<vector<int>> dp(k+1,vector<int>(n+1));
		dp[0][0]=1;
		for(int i=0;i<k;i++){
			for(int j=0;j<n;j++){
				if(j+1<c[i])continue;
				for(int l=-1;l<j;l++){
					if(l>j-c[i])break;
					if(l>=0&&l==j-c[i])continue;
					if(s0[j+1]-s0[j+1-c[i]]>0||s1[j+1-c[i]]-s1[l+1]>0)continue;
					dp[i+1][j+1]|=dp[i][l+1];
				}
				if(i+1==k&&dp[i+1][j+1]){
					if(s1[n]-s1[j+1]==0){
						return true;
					}
				}
			}
		}
		return false;
	};
	string t=s;
	for(int i=0;i<n;i++){
		if(s[i]=='_'||s[i]=='X')continue;
		s[i]='_';
		int f1=check();
		s[i]='X';
		int f2=check();
		s[i]='.';
		if(f1&&f2){
			t[i]='?';
		}else if(f1){
			t[i]='_';
		}else if(f2){
			t[i]='X';
		}
	}
    return t;
}

• 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