Submission #131199

#	Time	Username	Problem	Language	Result	Execution time	Memory
131199		nikolapesic2802	Paint By Numbers (IOI16_paint)	C++14	100 / 100	410 ms	43364 KiB

paint

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

int n, k;
bool L[205][200005];
bool R[205][200005];
char t[200005];

int ok_empty[200005], ok_full[200005];
int psum[200005];

bool has_white(int s, int e){
	return psum[e] != psum[s-1];
}

string solve_puzzle(string s, vector<int> c) {
	n = s.size();
	k = c.size();
	for(int i=1; i<=n; i++){
		t[i] = s[i-1];
	}
	t[n+1] = '_';
	n++;
	for(int i=1; i<=n; i++){
		psum[i] = psum[i-1] + (t[i] == '_');
	}
	L[0][0] = 1;
	for(int i=0; i<=k; i++){
		for(int j=1; j<=n; j++){
			if(t[j] == 'X') continue;
			L[i][j] = L[i][j-1];
			if(i > 0 && j >= c[i-1] + 1 && !has_white(j - c[i-1], j - 1)){
				L[i][j] |= L[i-1][j - c[i-1] - 1];
			}
		}
	}
	R[k][n+1] = 1;
	for(int i=k; i>=0; i--){
		for(int j=n; j; j--){
			if(t[j] != 'X') R[i][j] = R[i][j+1];
			if(i < k && j + c[i] <= n && t[j + c[i]] != 'X' && !has_white(j, j + c[i] - 1)){
				R[i][j] |= R[i+1][j + c[i] + 1];
			}
		}
	}
	for(int i=1; i<n; i++){
		for(int j=0; j<=k; j++){
			if(L[j][i] && R[j][i+1] && t[i] != 'X'){
				ok_empty[i] = 1;
			}
		}
	}
	for(int i=1; i<=k; i++){
		for(int j=0; j<=n-1-c[i-1]; j++){
			if(L[i-1][j] && R[i][j + c[i-1] + 2] && !has_white(j+1, j+c[i-1]) && t[j] != 'X' && t[j + c[i-1] + 1] != 'X'){
				ok_full[j+1]++;
				ok_full[j+c[i-1]+1]--;
			}
		}
	}
	for(int i=1; i<=n; i++){
		ok_full[i] += ok_full[i-1];
	}
	string dap;
	for(int i=1; i<n; i++){
		if(ok_empty[i] && ok_full[i]) dap.push_back('?');
		else if(ok_empty[i]) dap.push_back('_');
		else if(ok_full[i]) dap.push_back('X');
		else assert(0);
	}
	return dap;
}

• 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