Submission #292525

#	Time	Username	Problem	Language	Result	Execution time	Memory
292525		MoNsTeR_CuBe	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2087 ms	176068 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;

int n;
int maxK;
vector <int > c;
#define int long long 
vector< vector <int > > memo;

vector< int > pref;

vector<int> w;
vector<int> b;

vector< int > prefB;

string s;

bool dp(int position, int k){
	if(k == maxK){
		if(position < n){
			if(s[position] == 'X') return false;
			if(dp(position+1, k)){
				w[position] = true;
				return true;
			}else{
				return false;
			}
		}
	}
	if(k >= maxK) return true;
	if(position >= n){
		return false;
	}
	if(memo[position][k] != -1){
		return memo[position][k];
	}
	
	memo[position][k] = 0;
	if(s[position] != 'X'){
		w[position] |= dp(position+1, k);
		memo[position][k] |= dp(position+1, k);
	}
	int deb = 0;
	if(position >= 1) deb = pref[position-1];
	if(pref[position+c[k]-1]-deb == 0 && (position == 0 || s[position-1] != 'X') && (position+c[k] >= n || s[position+c[k]] != 'X') && position+c[k]-1 < n){
		bool ok = dp(position+c[k]+1, k+1);
		if(ok){
			
			prefB[position]++;
			if(position+c[k] < n) prefB[position+c[k]]--;
			if(position) w[position-1] = true;
			if(position+c[k] < n) w[position+c[k]] = true;
			memo[position][k] |= dp(position+c[k]+1, k+1);
		}
	}
	//cout << "DP " << position << ' ' << k << ' ' << memo[position][k] << endl;
	return memo[position][k];
}
#undef int
std::string solve_puzzle(std::string S, std::vector<int> C) {
    #define int long long
    n = S.size();
    maxK = C.size();
    memo.resize(n, vector< int > (maxK));
    for(int i = 0 ; i < n; i++){
		for(int j = 0; j < maxK; j++){
			memo[i][j] = -1;
		}
	}
    c=C;
    s = S;
    prefB.resize(n,0);
    pref.resize(n,0);
    b.resize(n,0);
    w.resize(n,0);
    for(int i = 0; i<n; i++){
		if(i) pref[i] += pref[i-1];
		pref[i] += (s[i] == '_');
	}
	dp(0,0);
	int curr = 0;
	for(int i = 0; i < n; i++){
		curr += prefB[i];
		if(curr) b[i] = true;
	}
	string ans = "";
	for(int i = 0; i < n; i++){
		if(b[i] && w[i]){
			ans += '?';
		}else if(w[i]){
			ans += '_';
		}else if(b[i]){
			ans += 'X';
		}
	}
	return ans;
	
}

• 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: 0 / 10