Submission #586911

#	Time	Username	Problem	Language	Result	Execution time	Memory
586911		AngusRitossa	Paint By Numbers (IOI16_paint)	C++14	100 / 100	588 ms	130288 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n, k, isblack[200010], iswhite[200010], mxwhite[200010], mxblack[200010], cblack[200010], cwhite[200010], clues[200010];
bool done[200010][110];
int memo[200010][110];
int dp(int a, int b)
{
//	printf("%d %d\n", a, b);
	if (a >= n && b != k) return 0;
	if (a >= n && b == k) return 1;
	if (b == k)
	{
		int w = cblack[n-1];
		if (a) w -= cblack[a-1];
		if (!w)
		{
			mxwhite[a] = max(mxwhite[a], n);
		}
	//	printf("%d %d %d\n", a, b, !w);
		return !w;
	}
	if (done[a][b]) return memo[a][b];
	done[a][b] = 1;
	int sz = clues[b];
	int poss = 0;
	if (!isblack[a]) poss = dp(a+1, b);
	if (poss) mxwhite[a] = max(mxwhite[a], 1);
	if (a + sz > n) return memo[a][b] = poss;
	int w = cwhite[a+sz-1];
	if (a) w -= cwhite[a-1];
	if (w) return memo[a][b] = poss;
	if (isblack[a+sz]) return memo[a][b] = poss;
//	printf(" ab %d %d\n", a, b);
	if (!dp(a+sz+1, b+1)) return memo[a][b] = poss;
//	printf("ab %d %d\n", a, b);
	poss = 1;
	mxblack[a] = max(mxblack[a], sz);
	mxwhite[a+sz] = max(mxwhite[a+sz], 1);
	return memo[a][b] = poss;
}
string solve_puzzle(string s, vector<int> c) {
    n = s.size();
    k = c.size();
    for (int i = 0; i < k; i++) clues[i] = c[i];
    for (int i = 0; i < n; i++)
    {
    	if (s[i] == 'X') isblack[i] = 1;
    	if (s[i] == '_') iswhite[i] = 1;
    	if (i) cblack[i] = cblack[i-1];
    	if (i) cwhite[i] = cwhite[i-1];
    	cwhite[i] += iswhite[i];
    	cblack[i] += isblack[i];
    }
    int poss = dp(0, 0);
    priority_queue<int> pq;
    for (int i = 0; i < n; i++)
    {
    //	printf("%d : %d\n", i, mxwhite[i]);
    	pq.push(-(i + mxwhite[i]));
    	while (!pq.empty() && -pq.top() <= i) { pq.pop(); }
    	if (pq.size()) iswhite[i] = 1;
    }
    while (pq.size()) pq.pop();
    for (int i = 0; i < n; i++)
    {
  //  	printf("%d : %d\n", i, mxblack[i]);
    	pq.push(-(i + mxblack[i]));
    	while (!pq.empty() && -pq.top() <= i) { pq.pop(); }
    	if (pq.size()) isblack[i] = 1;
    }
    string ans;
    for (int i = 0; i < n; i++)
    {
    //	printf("%d %d\n", iswhite[i], isblack[i]);
    	if (iswhite[i] && isblack[i]) ans.push_back('?');
    	else if (iswhite[i]) ans.push_back('_');
    	else if (isblack[i]) ans.push_back('X');
    //	else assert(false);
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:55:9: warning: unused variable 'poss' [-Wunused-variable]
   55 |     int poss = dp(0, 0);
      |         ^~~~

• 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