Submission #135470

#	Time	Username	Problem	Language	Result	Execution time	Memory
135470		MAMBA	Paint By Numbers (IOI16_paint)	C++17	59 / 100	2 ms	380 KiB

paint

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

using namespace std;

#define rep(i , j ,k) for(int i = j; i < (int)k; i++)

typedef vector<int> vi;

const int N = 2e5 + 10;

bitset<110> dp[N] , pd[N];

string solve_puzzle(string s, vi c) {
	int n = s.size();
	int k = c.size();

	rep(i , 0 , n) {
		dp[i].reset();
		pd[i].reset();
	}

	{
		int last = -1;
		bool haveX = false;
		rep(i , 0 , n) {
			if (s[i] == 'X') haveX = true;
			dp[i][0] = !haveX;
			if (s[i] == '_') last = i;

			rep(j , 1 , k + 1) {
				if (i && s[i] != 'X') dp[i][j] = dp[i - 1][j];
				int p = i - c[j - 1];
				if (last <= p) {
					if (p == -1)
						dp[i][j] = (j == 1);
					else if (p == 0)
						dp[i][j] = (j == 1 && s[p] != 'X');
					else 
						dp[i][j] = (s[p] != 'X' && dp[p - 1][j - 1]);
				}
			}
		}
	}

	{
		int last = n;
		bool haveX = false;
		for (int i = n - 1; ~i; i--) {
			if (s[i] == 'X') haveX = true;
			pd[i][k + 1] = !haveX;
			if (s[i] == '_') last = i;

			rep(j , 1 , k + 1) {
				int p = i + c[j - 1];
				if (i + 1 < n && s[i] != 'X') pd[i][j] = pd[i + 1][j];
				if (p <= last) {
					if (p == n)
						pd[i][j] = (j == k);
					else if (p == n - 1)
						pd[i][j] = (j == k && s[p] != 'X');
					else 
						pd[i][j] = (s[p] != 'X' && pd[p + 1][j + 1]);
				}
			}
		}
	}

	vi cnt(n + 1);

	rep(j , 1 , k + 1) {
		int last = -1;
		rep(i , 0 , n) {
			if (s[i] == '_') last = i;
			int p = i - c[j - 1];
			if (last <= p) {
				bool flag = true;
				if (flag && p == -1) {
					if (j > 1)
						flag = false;
				}
				else if (flag) {
					if (s[p] == 'X')
						flag = false;
					if (p == 0) {
						if (j > 1) flag = false;
					}
					else if (!dp[p - 1][j - 1]) flag = false;
				}

				p = i + 1;
				
				if (p == n) {
					if (j < k) flag = false;	
				}
				else if (flag) {
					if (s[p] == 'X') flag = false;
					if (p == n - 1) {
						if (j < k) flag = false;
					}
					else if (!pd[p + 1][j + 1]) flag = false;
				}

				if (flag) {
					cnt[i - c[j - 1] + 1]++;
					cnt[i + 1]--;
				}
			}
		}
	}



	string res;

	int local = 0;
	rep(i , 0 , n) {
		local += cnt[i];
		bool A = local > 0;
		bool B = false;
		rep(j , 0 , k + 1) {
			bool C = true;
			if (i == 0 && j) C = false;
			if (i == n - 1 && j < k) C = false;
			if (i && !dp[i - 1][j]) C= false;
			if (i + 1 < n && !pd[i + 1][j + 1]) C = false;
			B |= C;
		}
		if (s[i] == 'X') B = false;
		if (A && !B) res.push_back('X');
		else if (!A && B) res.push_back('_');
		else res.push_back('?');
		//assert(A || B);
	}

	return res;

}

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