Submission #641973

#	Time	Username	Problem	Language	Result	Execution time	Memory
641973		QwertyPi	Paint By Numbers (IOI16_paint)	C++14	100 / 100	311 ms	42968 KiB

paint

#include "paint.h"

#include <cstdlib>

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

bool dpf[101][200002], dpb[101][200002];

string s; int n; int ps_b[200002], ps_w[200002];
inline bool empty(int l, int r) { if(l < 1 || l > n || r < 1 || r > n) return false; return ps_b[r] == ps_b[l - 1]; }
inline bool fill(int l, int r) { if(l < 1 || l > n || r < 1 || r > n) return false; return ps_w[r] == ps_w[l - 1]; }

int aps_b[200002];

std::string solve_puzzle(std::string s, std::vector<int> c) {
	s = "_" + s + "$"; n = s.size() - 2;
	for(int i = 1; i <= n; i++) ps_b[i] = ps_b[i - 1] + (s[i] == 'X');
	for(int i = 1; i <= n; i++) ps_w[i] = ps_w[i - 1] + (s[i] == '_'); 
	int k = c.size(); vector<int> a; a.push_back(0);
	for(int i = 0; i < k; i++) { a.push_back(c[i]); };
	dpf[0][0] = dpb[k + 1][n + 1] = true;
	
	for(int i = 0; i <= k; i++){
		for(int j = 1; j <= n; j++){
			dpf[i][j] |= dpf[i][j - 1] && empty(j, j);
			if(i == 1){
				if(j >= a[i]) 
					dpf[i][j] |= dpf[i - 1][j - a[i]] && fill(j - a[i] + 1, j);
			}else if(i > 1){
				if(j >= a[i] + 1)
					dpf[i][j] |= dpf[i - 1][j - a[i] - 1] && empty(j - a[i], j - a[i]) && fill(j - a[i] + 1, j);
			}
		}
	}
	for(int i = k + 1; i >= 1; i--){
		for(int j = n; j >= 1; j--){
			dpb[i][j] |= dpb[i][j + 1] && empty(j, j);
			if(i == k){
				if(j <= n - a[i] + 1) 
					dpb[i][j] |= dpb[i + 1][j + a[i]] && fill(j, j + a[i] - 1);
			}else if(i < k){
				if(j <= n - a[i])
					dpb[i][j] |= dpb[i + 1][j + a[i] + 1] && empty(j + a[i], j + a[i]) && fill(j, j + a[i] - 1);
			}
		}
	}
	string ans(n, ' ');
	for(int i = 1; i <= k; i++){
		for(int j = 1; j <= n; j++){
			bool ok = true;
			ok &= fill(j, j + a[i] - 1);
			int f = j - (i != 1), b = j + a[i] - 1 + (i != k);
			if(i != 1) ok &= empty(j - 1, j - 1);
			if(i != k) ok &= empty(j + a[i], j + a[i]);
			if(!ok) continue;
			if(dpf[i - 1][f - 1] && dpb[i + 1][b + 1]){
				aps_b[j]++, aps_b[j + a[i]]--;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		aps_b[i] += aps_b[i - 1];
	}
	for(int i = 1; i <= n; i++){
		if(s[i] != '.'){
			ans[i - 1] = s[i];
			continue;
		}
		bool can_b = aps_b[i], can_w = false;
		for(int j = 0; j <= k; j++){
			if(dpf[j][i - 1] && dpb[j + 1][i + 1]){
				can_w = true;
			}
		}
		ans[i - 1] = (can_b ? (can_w ? '?' : 'X') : (can_w ? '_' : '$'));
	}
	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: 10 / 10