Submission #282294

#	Time	Username	Problem	Language	Result	Execution time	Memory
282294		AKaan37	Paint By Numbers (IOI16_paint)	C++17	90 / 100	1558 ms	524288 KiB

paint

//Bismillahirrahmanirrahim

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

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,PS[li],beyaz[li],siyah[li],dp[li][105],vis[li][105];
int cev;
string ss;

inline int f(int sira,int kac,std::string s,vector<int> c){
	int cevv=0;
	if(sira>=n){
		if(kac==m)return 1;
		return 0;
	}
	if(~dp[sira][kac])return dp[sira][kac];
	if(s[sira]=='X'){
		if(kac<m)if(PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac] && sira+c[kac]<=n && (sira+c[kac]>=n || s[sira+c[kac]]!='X'))cevv=max(cevv,f(sira+c[kac]+1,kac+1,s,c));
	}
	else{
		if(s[sira]!='_')if(kac<m)if(PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac] && sira+c[kac]<=n && (sira+c[kac]>=n || s[sira+c[kac]]!='X'))cevv=max(cevv,f(sira+c[kac]+1,kac+1,s,c));
		cevv=max(cevv,f(sira+1,kac,s,c));
	}
	return dp[sira][kac]=cevv;
}

inline void yaz(int sira,int kac,string s,vector<int> c){
	//~ cout<<sira<<" : : "<<kac<<endl;
	if(sira>=n){
		return ;
	}
	if(vis[sira][kac])return;
	vis[sira][kac]=1;
	if(s[sira]=='X'){
		for(int i=sira;i<sira+c[kac];i++)siyah[i]=1;
		beyaz[sira+c[kac]]=1;
		yaz(sira+c[kac]+1,kac+1,s,c);
	}
	else if(s[sira]=='_'){
		beyaz[sira]=1;
		yaz(sira+1,kac,s,c);
	}
	else{
		if(kac<m){
			if(sira+c[kac]+1>=n && PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac] && (sira+c[kac]>=n || s[sira+c[kac]]!='X')){
				for(int i=sira;i<sira+c[kac];i++)siyah[i]=1;
				beyaz[sira+c[kac]]=1;
				yaz(sira+c[kac]+1,kac+1,s,c);
			}
		}
		if(kac==m && sira==n-1){
			beyaz[sira]=1;
			yaz(sira+1,kac,s,c);
		}
		if(kac<m){
			if(sira+c[kac]+1<n){
				if(dp[sira+c[kac]+1][kac+1]==1 && PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac] && (sira+c[kac]>=n || s[sira+c[kac]]!='X')){
					for(int i=sira;i<sira+c[kac];i++)siyah[i]=1;
					beyaz[sira+c[kac]]=1;
					yaz(sira+c[kac]+1,kac+1,s,c);
				}
			}
		}
		if(sira+1<n){
			if(s[sira]!='X'){
				if(dp[sira+1][kac]==1){
					beyaz[sira]=1;
					yaz(sira+1,kac,s,c);
				}
			}
		}
	}
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
	memset(dp,-1,sizeof(dp));
	n=(int)s.size();
	m=(int)c.size();
	for(int i=0;i<n;i++){
		if(i==0){
			if(s[i]!='_')PS[i]=1;
			continue;
		}
		PS[i]=PS[i-1];
		if(s[i]!='_')PS[i]++;
	}
	PS[n]=PS[n-1];
	PS[n+1]=PS[n-1];
	PS[n+2]=PS[n-1];
	f(0,0,s,c);
	yaz(0,0,s,c);
	for(int i=0;i<n;i++){
		if(s[i]=='X')ss+='X';
		else if(s[i]=='_')ss+='_';
		else if(beyaz[i] && siyah[i])ss+='?';
		else if(beyaz[i])ss+='_';
		else if(siyah[i])ss+='X';
	}
	//~ cout<<"**\n";
	//~ cout<<ss.size()<<endl;
	return ss;
}

• 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: 0 / 10