Submission #96295

#	Time	Username	Problem	Language	Result	Execution time	Memory
96295		figter001	Paint By Numbers (IOI16_paint)	C++14	100 / 100	639 ms	104676 KiB

paint

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

using namespace std;

typedef long long ll;
const int maxn = 2e5+50;
const int maxk = 110;

int n;
vector<int> c;
string s;
int dp[maxn][maxk],sum[maxn];
bool can[maxn][2];

int calc(int idx,int at){
	if(idx >= n)return (at == (int)c.size());
	int &res = dp[idx][at];
	if(res != -1)return res;
	res = 0;
	if(s[idx] == 'X'){
		if(at == c.size())return res;
		int to = idx + c[at] - 1;
		if(to >= n)return res;
		int cur = sum[to];
		if(idx)cur -= sum[idx-1];
		if(cur)return res = 0;
		if(s[to + 1] == 'X')return res = 0;
		res = calc(to+2,at+1);
		if(res){
			can[to+1][1] = 1;
			for(int i=idx;i<=to;i++)can[i][0] = 1;
		}
	}
	else if(s[idx] == '_'){
		res = calc(idx+1,at);
	}else{
		res = calc(idx+1,at);
		if(res)can[idx][1] = 1;
		if(at != c.size()){
			int to = idx + c[at] - 1;
			if(to < n){
				int cur = sum[to];
				if(idx)cur -= sum[idx-1];
				if(!cur){
					if(s[to + 1] != 'X'){
						res |= calc(to+2,at+1);
						if(calc(to+2,at+1)){
							can[to+1][1] = 1;
							for(int i=idx;i<=to;i++)can[i][0] = 1;
						}
					}
				}
			}
		}
	}
	return res;
}

string solve_puzzle(string S, vector<int> C){
	memset(dp,-1,sizeof(dp));
	n = S.size();
	c = C;
	s = S;
	for(int i=0;i<n;i++){
		sum[i] = s[i] == '_';
		if(i)sum[i]+=sum[i-1];
	}
	calc(0,0);
	string ans;
	for(int i=0;i<n;i++){
		if(s[i] == '.'){
			if(can[i][0] && can[i][1])ans += '?';
			else if(can[i][1])ans += '_';
			else ans += 'X';
		}else ans += s[i];
	}
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int calc(int, int)':
paint.cpp:22:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(at == c.size())return res;
      ~~~^~~~~~~~~~~
paint.cpp:40:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(at != c.size()){
      ~~~^~~~~~~~~~~

• 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