Submission #741375

#	Time	Username	Problem	Language	Result	Execution time	Memory
741375		Abrar_Al_Samit	Paint By Numbers (IOI16_paint)	C++17	100 / 100	284 ms	167564 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;

	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;
	}
	prev_white[0] = prev_black[0] = -1;
	prev_white[n+1] = lst_white;
	prev_black[n+1] = lst_black;

	//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+1<=n && s[i+1]=='X') continue;

			if(i>=c[j] && prev_white[i+1]<=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 && s[i-c[j]]!='X') 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+1]<i) suff[i][j] = 1;
			} else {
				if(s[i]!='X') {
					suff[i][j] |= suff[i+1][j];
				}
				if(s[i-1]=='X') continue;

				if(i+c[j+1]-1<=n && prev_white[i+c[j+1]]<i) {
					if(s[i+c[j+1]]!='X') 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] && s[i+1+c[0]]!='X') 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]!='_' && (i==n || s[i+1]!='X')) {
		for(int j=0; j<k; ++j) {
			if(i>=c[j] && prev_white[i+1]<=i-c[j] && suff[i+2][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] && s[i-c[j]]!='X') {
						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 if(can_black[i]) { //for stress testing purposes
				ret += 'X';
			} else {
				ret = "NO SOLUTION";
				return ret;
			}
		} else {
			ret += s[i];
		}
	}
	return ret;
}

• 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