Submission #396932

#	Time	Username	Problem	Language	Result	Execution time	Memory
396932		alishahali1382	Paint By Numbers (IOI16_paint)	C++14	100 / 100	328 ms	44412 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
 
const int inf=1000001000;
const int MAXN=200010, K=103;
 
int n, m, k;
bool dp[MAXN][K], pd[MAXN][K];
int C[K];
int ps[MAXN][2], res[MAXN];
string S, ans;

bool check(int i, int j, int t){
	int l=i-t, r=i-t+1+C[j];
	if (r>n+1 || S[l]=='X' || S[r]=='X' || ps[r-1][0]!=ps[l][0]) return 0;
	if (l && !dp[l-1][j-1]) return 0;
	if (!l && j>1) return 0;
	if (r<=n && !pd[r+1][j+1]) return 0;
	if (r==n+1 && j<k) return 0;
	return 1;
}

string solve_puzzle(string _S, vector<int> _C) {
	S=_S;
	n=S.size();
	S="#"+S+"#";
	for (int i=1; i<=n+1; i++){
		ps[i][0]=ps[i-1][0];
		ps[i][1]=ps[i-1][1];
		if (S[i]=='_') ps[i][0]++;
		if (S[i]=='X') ps[i][1]++;
	}
	k=_C.size();
	for (int i=1; i<=k; i++) C[i]=_C[i-1];
	dp[0][0]=1;
	for (int i=1; i<=n; i++){
		if (S[i]!='X'){
			for (int j=0; j<=k; j++)
				dp[i][j]=dp[i-1][j];
		}
		for (int j=1; j<=k; j++) if (C[j]<=i){
			if (ps[i][0]==ps[i-C[j]][0] && S[i-C[j]]!='X')
				dp[i][j]|=dp[i-C[j]-(C[j]<i)][j-1];
		}
	}
	pd[n+1][k+1]=1;
	for (int i=n; i; i--){
		if (S[i]!='X'){
			for (int j=1; j<=k+1; j++)
				pd[i][j]=pd[i+1][j];
		}
		for (int j=1; j<=k; j++) if (i+C[j]<=n+1){
			if (ps[i-1][0]==ps[i+C[j]-1][0] && S[i+C[j]]!='X')
				pd[i][j]|=pd[min(n+1, i+C[j]+1)][j+1];
		}
	}
	for (int i=1; i<=n; i++) for (int j=1; j<=k; j++) if (check(i, j, 1)) res[i]++, res[i+C[j]]--;
	for (int i=1; i<=n; i++) res[i]+=res[i-1];
	for (int i=1; i<=n; i++){
		if (S[i]!='.'){
			ans+=S[i];
			continue ;
		}
		int f0=0, f1=0;
		for (int j=0; j<=k; j++){
			if (dp[i-1][j] && pd[i+1][j+1]){
				f0=1;
				break ;
			}
		}
		if (res[i]) f1=1;
		if (f0+f1==1){
			if (f0) ans+='_';
			else ans+='X';
		}
		else ans+='?';
	}
	return ans;
}

• 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