Submission #53005

#	Time	Username	Problem	Language	Result	Execution time	Memory
53005		KieranHorgan	Paint By Numbers (IOI16_paint)	C++17	100 / 100	904 ms	102816 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int n, k;
string s;
vector<int> c;

int dp[200005][105];
int whitePre[200005];
int canWhite[200005];
int canBlack[200005];

bool solve(int idx, int sub) {
	if(idx > n) return sub==k;
	if(dp[idx][sub] != -1) return dp[idx][sub];
	if(sub == k) {
		if(s[idx] == 'X') return dp[idx][sub] = 0;
		if(solve(idx+1, sub))
			return dp[idx][sub] = canWhite[idx] = 1;
		return dp[idx][sub] = 0;
	}
	if(idx+c[sub]-1 > n || s[idx-1] == 'X' || s[idx+c[sub]] == 'X') {
		if(s[idx] == 'X') return dp[idx][sub] = 0;
		if(solve(idx+1, sub))
			return dp[idx][sub] = canWhite[idx] = 1;
		return dp[idx][sub] = 0;
	}
	if(whitePre[idx+c[sub]-1]-whitePre[idx-1] != 0) {
		if(s[idx] == 'X') return dp[idx][sub] = 0;
		if(solve(idx+1, sub))
			return dp[idx][sub] = canWhite[idx] = 1;
		return dp[idx][sub] = 0;
	}

	bool ok = 0;
	if(s[idx] != 'X' && solve(idx+1, sub)) {
		canWhite[idx] = ok = 1;
	}
	if(solve(idx+c[sub]+1, sub+1)) {
		canWhite[idx-1] = 1;
		canWhite[idx+c[sub]] = 1;
		canBlack[idx]++;
		canBlack[idx+c[sub]]--;
		ok = 1;
	}
	return dp[idx][sub] = ok;
}

string solve_puzzle(string S, vector<int> C) {
	s = "_" + S + "_"; c = C;
	n = S.size(); k = C.size();

	memset(dp, -1, sizeof(dp));
	for(int i = 1; i <= n; i++)
		whitePre[i] = whitePre[i-1]+(s[i]=='_');

	solve(1, 0);

	for(int i = 1; i <= n; i++)
		canBlack[i] += canBlack[i-1];

	string res;
	for(int i = 1; i <= n; i++)
		if(canBlack[i] && canWhite[i])
			res.push_back('?');
		else if(canBlack[i])
			res.push_back('X');
		else
			res.push_back('_');
    return res;
}

Compilation message (stderr)

paint.cpp: In function 'bool solve(int, int)':
paint.cpp:18:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(s[idx] == 'X') return dp[idx][sub] = 0;
                            ~~~~~~~~~~~~~^~~
paint.cpp:20:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    return dp[idx][sub] = canWhite[idx] = 1;
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:21:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   return dp[idx][sub] = 0;
          ~~~~~~~~~~~~~^~~
paint.cpp:24:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(s[idx] == 'X') return dp[idx][sub] = 0;
                            ~~~~~~~~~~~~~^~~
paint.cpp:26:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    return dp[idx][sub] = canWhite[idx] = 1;
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:27:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   return dp[idx][sub] = 0;
          ~~~~~~~~~~~~~^~~
paint.cpp:30:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(s[idx] == 'X') return dp[idx][sub] = 0;
                            ~~~~~~~~~~~~~^~~
paint.cpp:32:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    return dp[idx][sub] = canWhite[idx] = 1;
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:33:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   return dp[idx][sub] = 0;
          ~~~~~~~~~~~~~^~~
paint.cpp:47:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return dp[idx][sub] = ok;
         ~~~~~~~~~~~~~^~~~

• 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