Submission #97040

#	Time	Username	Problem	Language	Result	Execution time	Memory
97040		youngyojun	Paint By Numbers (IOI16_paint)	C++11	100 / 100	336 ms	15096 KiB

paint

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

const int MAXN = 200055;
const int MAXK = 105;

bitset<MAXK> DA[2][MAXN], DB[2][MAXN];
int S[MAXN];

char A[MAXN];
int B[MAXK];

int N, K;

void reverse() {
	reverse(A+1, A+N+1);
	reverse(B+1, B+K+1);
}

void run(bitset<MAXK> DA[], bitset<MAXK> DB[]) {
	DA[0][0] = true;
	for(int i = 1; i <= N; i++) {
		S[i] = S[i-1] + ('_' == A[i]);
		for(int j = 0; j <= K; j++)
			DA[i][j] = 'X' != A[i] && (DA[i-1][j] || DB[i-1][j]);
		for(int j = 1; j <= K; j++)
			DB[i][j] = B[j] <= i && DA[i-B[j]][j-1] && S[i] == S[i-B[j]];
	}
}

string getAns() {
	run(DA[0], DB[0]); reverse();
	run(DA[1], DB[1]); reverse();
	memset(S, 0, (N+1)<<2);
	for(int j = 1; j <= K; j++) {
		for(int s = 1, e = B[j]; e <= N; s++, e++) {
			if(!DB[0][e][j] || !DB[1][N-s+1][K-j+1]) continue;
			S[s]++; S[e+1]--;
		}
	}
	string ret;
	for(int i = 1; i <= N; i++) {
		S[i] += S[i-1];
		if(!S[i]) {
			ret.pb('_');
			continue;
		}
		bool t = false;
		for(int j = 0; j <= K; j++) {
			if(!DA[0][i][j] || !DA[1][N-i+1][K-j]) continue;
			t = true;
			break;
		}
		ret.pb(t ? '?' : 'X');
	}
	return ret;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
	::N = s.length(); ::K = c.size();
	for(int i = 0; i < ::N; i++) ::A[i+1] = s[i];
	for(int i = 0; i < ::K; i++) ::B[i+1] = c[i];
	return getAns();
}

• 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