Submission #741319

#	Time	Username	Problem	Language	Result	Execution time	Memory
741319		Abrar_Al_Samit	Paint By Numbers (IOI16_paint)	C++17	0 / 100	2 ms	1876 KiB

paint

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

const int nax = 2e5 + 10;
int n, k;
int pref[nax][104], suff[nax][104];

int can_black[nax], can_white[nax];
int prev_white[nax], prev_black[nax];

string solve_puzzle(string s, vector<int> c) {
	//initialize 
	n = s.size(), k = c.size();
	s = '@' + s;
	memset(prev_white, -1, sizeof prev_white);
	memset(prev_black, -1, sizeof prev_black);

	int lst_white = -1, lst_black = -1;
	for(int i=1; i<=n; ++i) {
		prev_black[i] = lst_black;
		prev_white[i] = lst_white;

		if(s[i]=='X') lst_black = i;
		if(s[i]=='_') lst_white = i;
	}

	//build pref
	for(int i=1; i<=n; ++i) {
		for(int j=0; j<k; ++j) {
			if(s[i]!='X') {
				pref[i][j] |= pref[i-1][j];
			}

			if(i>=c[j] && prev_white[i]<=i-c[j]) {
				if(j==0) {
					if(prev_black[i-c[j]+1]==-1) pref[i][j] = 1;
				} else {
					if(i-c[j]-1>0) pref[i][j] |= pref[i-c[j]-1][j-1];
				}
			}
		}
	}

	//build suff
	for(int i=n+1; i<min(nax, n+10); ++i) {
		suff[i][k-1] = 1;
	}
	for(int i=n; i>=1; --i) {
		for(int j=0; j<k; ++j) {
			if(j==k-1) {
				if(prev_black[n]<i) suff[i][j] = 1;
			} else {
				if(s[i]!='X') {
					suff[i][j] |= suff[i+1][j];
				}

				if(i+c[j+1]-1<=n && prev_white[i+c[j+1]]<i) {
					suff[i][j] |= suff[i+c[j+1]+1][j+1];
				}
			}
		}
	}

	//check white
	for(int i=1; i<=n; ++i) if(s[i]=='.') {
		for(int j=0; j<k; ++j) {
			if(pref[i-1][j] && suff[i+1][j]) can_white[i] = 1;
		}
	}
		//handle full suffix
		int mxpr = 0;
		for(int i=1; i<=n; ++i) {
			if(s[i]=='X') break;

			if(i+1+c[0]-1<=n && prev_white[i+1+c[0]]<=i) {
				if(suff[i+1+c[0]+1][0]) mxpr = i;
			}
		}
		for(int i=1; i<=mxpr; ++i) {
			can_white[i] = 1;
		}

	//check black
	for(int i=1; i<=n; ++i) if(s[i]=='.') {
		for(int j=0; j<k; ++j) {
			if(i>=c[j] && prev_white[i]<=i-c[j]) {
				if(j==0) {
					if(prev_black[i-c[j]+1]==-1) {
						can_black[i-c[j]+1]++;
						can_black[i+1]--;
					}
				} else {
					if(i-c[j]-1>0 && pref[i-c[j]-1][j-1]) {
						can_black[i-c[j]+1]++;
						can_black[i+1]--;	
					}
				}
			}
		}
	}
	for(int i=1; i<n; ++i) {
		can_black[i] += can_black[i-1];
	}

	//prepare answer
	string ret;
	for(int i=1; i<=n; ++i) {
		if(s[i]=='.') {
			if(can_white[i] && can_black[i]) {
				ret += '?';
			} else if(can_white[i]) {
				ret += '_';
			} else {
				ret += 'X';
			}
		} else {
			ret += s[i];
		}
	}
	return ret;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10