Submission #154826

#	Time	Username	Problem	Language	Result	Execution time	Memory
154826		junodeveloper	Paint By Numbers (IOI16_paint)	C++14	100 / 100	646 ms	172236 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int a[200010],b[200010],cnt[200010][3],n,m;
int mem[200010][201];
int mx[200010],my[200010];
int solve(int n,int k) {
	if(!n) return !k;
	if(mem[n][k]!=-1) return mem[n][k];
	int& r=mem[n][k];
	if(a[n]==2) r=solve(n-1,k);
	else if(a[n]==1) {
		if(!k||n<b[k]) r=0;
		else if(cnt[n][2]-cnt[n-b[k]][2]>0) r=0;
		else if(n>b[k]&&a[n-b[k]]==1) r=0;
		else {
			if(n==b[k]) r=solve(0,k-1);
			else r=solve(n-b[k]-1,k-1);
			if(r) mx[n-b[k]+1]++,mx[n+1]--,my[n-b[k]]=1;
		}
	} else {
		r=solve(n-1,k);
		if(r) my[n]=1;
		if(!k||n<b[k]);
		else if(cnt[n][2]-cnt[n-b[k]][2]>0);
		else if(n>b[k]&&a[n-b[k]]==1);
		else {
			int t=0;
			if(n==b[k]) t=solve(0,k-1);
			else t=solve(n-b[k]-1,k-1);
			//printf("n:%d,k:%d,t:%d\n",n,k,t);
			if(t) {
				mx[n-b[k]+1]++,mx[n+1]--;
				my[n-b[k]]=1;
			}
			r|=t;
		}
	}
	return r;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
	n=s.length(); m=c.size();
	int i,j;
	memset(mem,-1,sizeof(mem));
	for(i=0;i<n;i++) {
		if(s[i]=='X') a[i+1]=1;
		else if(s[i]=='_') a[i+1]=2;
		for(j=0;j<3;j++)cnt[i+1][j]=cnt[i][j];
		cnt[i+1][a[i+1]]++;
	}
	for(i=0;i<m;i++) b[i+1]=c[i];
	solve(n,m);
	string ret="";
	for(i=1;i<=n;i++) {
		mx[i]+=mx[i-1];
		if(mx[i]>0&&my[i]>0) ret+="?";
		else if(mx[i]>0) ret+="X";
		else ret+="_";
	}
	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