Submission #570079

#	Time	Username	Problem	Language	Result	Execution time	Memory
570079		franfill	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1539 ms	106552 KiB

paint

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

int n, k;
string s;
vector < int > c;
vector < int > cnt_, cntX;
vector < int > inc_, incX;
vector < vector < int > > memo;

bool has_(int l, int r)
{
	r = min(r, n);
	return cnt_[r] > cnt_[l];
}

bool hasX(int l, int r)
{
	r = min(r, n);
	return cntX[r] > cntX[l];
}

void set_(int l, int r)
{
	inc_[l]++;
	inc_[r]--;
}

void setX(int l, int r)
{
	incX[l]++;
	incX[r]--;
}

bool verifica(int i, int j)
{
	if (j == k) if (!hasX(i, n))
	{
		set_(i, n);
		return 1;
	}
	else return 0;
	if (i >= n) return 0;
	if (i + c[j] >= n) return 0;
	if (memo[i][j] != -1) return memo[i][j];
	bool ok = false;
	if (!has_(i, i+c[j]) && s[i+c[j]] != 'X')
	{
		if (verifica(i+c[j]+1, j+1))
		{
			setX(i, i+c[j]);	
			set_(i+c[j], i+c[j]+1);
			ok = true;
		}
	}
	if (s[i] != 'X')
	{
		if (verifica(i+1, j))
		{
			set_(i, i+1);
			ok = true;
		}
	}
	//cerr << i << " " << j << " " << ok << "\n";
	return memo[i][j] = ok;
}

std::string solve_puzzle(std::string ss, std::vector<int> cc) 
{
	s = ss;
	s += "_";
	c = cc;
	n = s.size();	
	k = c.size();
	memo.resize(n, vector < int > (k, -1));

	cnt_.resize(n+1,0);
	cntX.resize(n+1,0);
	inc_.resize(n+1, 0);
	incX.resize(n+1, 0);
	for (int i = 1; i <= n; i++)
	{
		cnt_[i] = cnt_[i-1] + (s[i-1] == '_');
		cntX[i] = cntX[i-1] + (s[i-1] == 'X');
	}
	string ans = "";
	for (int i = 0; i < n; i++)
	{
		verifica(i, 0);
		if (s[i] == 'X') break;
	}
	int cX=0, c_=0;
	for (int i = 0; i < n-1; i++)
	{
		cX += incX[i];
		c_ += inc_[i];
		assert(cX || c_);
		assert(cX >= 0);
		assert(c_ >= 0);
		if (!cX) ans += "_";
		else if (!c_) ans += "X";
		else ans += "?";
	}
    return ans; 
}

Compilation message (stderr)

paint.cpp: In function 'bool verifica(int, int)':
paint.cpp:38:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   38 |  if (j == k) if (!hasX(i, n))
      |     ^
paint.cpp:66:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   66 |  return memo[i][j] = 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