Submission #620097

#	Time	Username	Problem	Language	Result	Execution time	Memory
620097		sofapuden	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1138 ms	101664 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>

using namespace std;

const int mxN = 2e5+5;
const int mxK = 1e2+5;

int dp[mxN][mxK];
int N, K;
vector<int> C;
string S;
vector<int> W, B;
vector<int> pW;

int f(int n, int k){
	if(n > N)return 0;
	if(n == N)return k == K;
	if(dp[n][k] != -1)return dp[n][k];
	if(S[n] == 'X'){
		if(k == K)return dp[n][k] = 0;
		if(n+C[k] > N)return dp[n][k] = 0;
		if(pW[n+C[k]-1] != (n ? pW[n-1] : 0))return dp[n][k] = 0;
		int se;
		if(n+C[k] == N)se = (k+1 == K);
		else if(S[n+C[k]] == 'X')return dp[n][k] = 0;
		else se = f(n+C[k]+1,k+1);
		if(se){B[n] = max(B[n],C[k]);W[n+C[k]]=1;}
		return dp[n][k] = se;
	}
	else if(S[n] == '_'){
		W[n] = 1;
		return dp[n][k] = f(n+1,k);
	}
	else{
		int fi;
		if(k == K)fi = 0;
		else if(n+C[k] > N)fi = 0;
		else if(pW[n+C[k]-1] != (n ? pW[n-1] : 0))fi = 0;
		else if(n+C[k] == N)fi = (k+1 == K);
		else if(S[n+C[k]] == 'X')fi = 0;
		else fi = f(n+C[k]+1,k+1);
		if(fi){B[n] = max(B[n],C[k]);if(n+C[k] != N)W[n+C[k]]=1;}
		int se = f(n+1,k);
		W[n] |= se;
		return dp[n][k] = fi|se;	
	}
}

string solve_puzzle(string s, vector<int> c) {
	S = s;
	C = c;
	N = s.size();
	K = c.size();
	W.resize(N,0);
	B.resize(N,0);
	pW.resize(N,0);
	for(int i = 0; i < N; ++i)pW[i] = (S[i] == '_') + (i ? pW[i-1] : 0);
	for(int i = 0; i < mxN; ++i)for(int j = 0; j < mxK; ++j)dp[i][j] = -1;
	f(0,0);
	int cn = 0;
	for(int i = 0; i < N; ++i){
		cn = max(cn-1,B[i]);
		if(W[i] && cn > 0)S[i] = '?';
		else if(W[i])S[i] = '_';
		else if(cn > 0)S[i] = 'X'; 
	}
	return S;
}

• 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