Submission #64718

#	Time	Username	Problem	Language	Result	Execution time	Memory
64718		mhnd	Paint By Numbers (IOI16_paint)	C++14	100 / 100	951 ms	102116 KiB

paint

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5+50;
const int K = 105;
const ll oo = 1e18;
const ll mod = 1e9+7;

string s;
vector<int> b;
int p[N],dp[N][K],n,c,x[N],u[N];

int check(int a,int b){
	return p[b] - (a>0?p[a-1]:0);
}

void update_x(int a,int b){
	x[a]++;
	x[b+1]--;
}

void update_u(int a,int b){
	u[a]++;
	u[b+1]--;
}

int calc(int i,int block){
	if(i >= n)return block == c;
	int &ret = dp[i][block];
	if(ret!=-1)return ret;
	ret = 0;
	if(block == c){
		if(s[i] == '_' || s[i] == '.'){
			ret = calc(i+1,block);
			if(ret)update_u(i,i);
		}
		return ret;
	}
	if(s[i] == 'X'){
		int to = i + b[block];
		if(to > n || (to < n && s[to] == 'X') || check(i,to-1))return ret;
		ret = calc(to+1,block+1);
		if(ret){
			if(to<n)update_u(to,to);
			update_x(i,to-1);
		}
		return ret;
	}
	if(s[i] == '_'){
		ret = calc(i+1,block);
		update_u(i,i);
		return ret;
	}
	bool no = calc(i+1,block),yes;
	int to = i + b[block];
	if(no)update_u(i,i);
	if(to > n || (to < n && s[to] == 'X') || check(i,to-1))yes = 0;
	else{
		yes = calc(to+1,block+1);
		if(yes){
			if(to < n)update_u(to,to);
			update_x(i,to-1);
		}
	}
	ret = yes|no;
	return ret;
}

string solve_puzzle(string s2,vector<int> c2){
	memset(dp,-1,sizeof(dp));
	s = s2;b = c2;
	n = s.size();c = b.size();
	for(int i=0;i<n;i++){
		if(i)p[i]=p[i-1];
		p[i] += s[i]=='_';
	}
	calc(0,0);
	string ans;
	for(int i=0;i<n;i++){
		if(i){
			x[i] += x[i-1];
			u[i] += u[i-1];
		}
		if(x[i] && u[i])ans += '?';
		else if(x[i])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