Submission #282302

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

paint

//Bismillahirrahmanirrahim

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

using namespace std;

typedef long long lo;
typedef pair< int,int > 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 = 200001;
const lo mod = 1000000007;

int n,m,k,flag,t,PS[li];
int cev;
map<int,int> dp[li],vis[li];
PII p[li];
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].find(kac)!=dp[sira].end())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++)p[i].se=1;
		p[sira+c[kac]].fi=1;
		yaz(sira+c[kac]+1,kac+1,s,c);
	}
	else if(s[sira]=='_'){
		p[sira].fi=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++)p[i].se=1;
				p[sira+c[kac]].fi=1;
				yaz(sira+c[kac]+1,kac+1,s,c);
			}
		}
		if(kac==m && sira==n-1){
			p[sira].fi=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++)p[i].se=1;
					p[sira+c[kac]].fi=1;
					yaz(sira+c[kac]+1,kac+1,s,c);
				}
			}
		}
		if(sira+1<n){
			if(s[sira]!='X'){
				if(dp[sira+1][kac]==1){
					p[sira].fi=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();
	int say=0;
	for(int i=0;i<(int)n;i++){
		if(s[i]=='.')say++;
	}
	if(say==n && k*k+1000<=n){
		for(int i=0;i<n;i++){ss+='?';}
		return ss;
	}
	s+='0';
	s+='0';
	s+='0';
	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(p[i].fi && p[i].se)ss+='?';
		else if(p[i].fi)ss+='_';
		else if(p[i].se)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