Submission #96289

#	Time	Username	Problem	Language	Result	Execution time	Memory
96289		figter001	Paint By Numbers (IOI16_paint)	C++14	0 / 100	61 ms	86392 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];
bool can[maxn][2];

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

string solve_puzzle(string S, vector<int> C){
	memset(dp,-1,sizeof(dp));
	n = S.size();
	c = C;
	s = S;
	calc(0,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, int)':
paint.cpp:17:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(at == c.size() && len)return 0;
     ~~~^~~~~~~~~~~
paint.cpp:19:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(at != c.size() && len == c[at] && idx == n)at++;
     ~~~^~~~~~~~~~~
paint.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(at == c.size() && len || len != c[at])return 0;
           ~~~^~~~~~~~~~~
paint.cpp:26:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   else if(at == c.size() && len || len != c[at])return 0;
           ~~~~~~~~~~~~~~~^~~~~~
paint.cpp:30:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(at == c.size() && len || len != c[at])res = 0;
           ~~~^~~~~~~~~~~
paint.cpp:30:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   else if(at == c.size() && len || len != c[at])res = 0;
           ~~~~~~~~~~~~~~~^~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10