Submission #77132

#	Time	Username	Problem	Language	Result	Execution time	Memory
77132		shoemakerjo	Paint By Numbers (IOI16_paint)	C++14	100 / 100	305 ms	49556 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;
#define maxn 200010
bool dp[maxn][101];

int zpref[maxn];

bool dback[maxn][101];

bool canx[maxn];
bool canblank[maxn];

int delt[maxn];

string solve_puzzle(string s, vector<int> c) {
	zpref[0] = 0;
	s = "." + s;
	int n = s.size()-1;
	int k = c.size();
	c.insert(c.begin(), 0);
	// for (int i = 1; i <= k; i++) {
	// 	cout << "c " << i << " :: " << c[i] << endl;
	// }
	for (int i = 1; i <= n; i++) {
		zpref[i] = zpref[i-1];
		if (s[i] == '_') zpref[i]++;
	}
	dp[0][0] = true;
	for (int i = 1; i <= n; i++) {
		
		if (s[i] != 'X') {
			for (int j = 0; j <= k; j++) {
				dp[i][j] |= dp[i-1][j];
			}
		}
		for (int j = 1; j  <= k; j++) {
			int prevo = i - c[j];
			if (prevo < 0) continue;
			// cout << "prevo: " << i << " " << j << " " << prevo << endl;

			//guy before the rang
			if (zpref[i] - zpref[prevo] > 0) continue;
			if (s[prevo] == 'X') continue;
			if (j == 1) {
				if (prevo == 0 || dp[prevo-1][j-1]) {
					dp[i][j] = true;
				}
				
				continue;
			}
			else if (prevo == 0) continue;

			if (dp[prevo-1][j-1]) dp[i][j] = true;
		}
	}

	dback[n+1][0] = true;
	for (int i = n; i >= 1; i--) {
		if (s[i] != 'X') {
			for (int j = 0; j <= k; j++) {
				dback[i][j] |= dback[i+1][j];
			}
		}
		for (int j = 1; j <= k; j++) {
			int afto = i + c[k+1-j]; //k+1-j is important here
			if (afto > n+1) continue;
			if (zpref[afto-1] - zpref[i-1] > 0) continue;
			if (s[afto] == 'X') continue;
			if (j == 1) {
				if (afto == n+1 || dback[afto+1][j-1]) {
					dback[i][j] = true;
					if (i - 2 < 0 && s[i-1] != 'X'
						&& j == k || 
						i - 2 >= 0 && dp[i-2][k-j] && s[i-1] != 'X') {
						// cout << i << " to " << afto << endl;
						delt[i]++;
						delt[afto]--;
					}
				}
				
				continue;
			}
			else if (afto == n+1) continue;
			if (dback[afto+1][j-1]) {
				dback[i][j] = true;
				if (i - 2 < 0 && s[i-1] != 'X' && 
					j == k || i -2 >= 0 && dp[i-2][k-j] && s[i-1] != 'X') {
					// cout << i << "to :: " << afto << endl;
					delt[i]++;
					delt[afto]--;
				}
			}
		}
	}

	int crun = 0;
	for (int i = 1; i <= n; i++) {
		// if (s[i] != '.') continue;
		crun += delt[i];
		if (crun) canx[i] = true;
		for (int j = 0;  j <= k; j++) {
			if (dp[i-1][j] && dback[i+1][k-j]) {
				// cout << "WE MADE IT" << endl;
				canblank[i] = true;
			}
		}
	}


	string ans;
	for (int i = 1; i <= n; i++) {

		// cout << i << " "  << canx[i] << " " << canblank[i] << endl;

		if (s[i] != '.') ans += s[i];
		else {
			if (canx[i] && canblank[i]) ans += '?';
			else if (canx[i]) ans += 'X';
			else ans += '_'; 
		}
	}

	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 0; j <= k; j++) {
	// 		cout << i << " " << j << " : " << dp[i][j] << endl;
	// 	}
	// }

    return ans;

}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:76:7: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (i - 2 < 0 && s[i-1] != 'X'
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~
       && j == k || 
       ^~~~~~~~~
paint.cpp:89:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (i - 2 < 0 && s[i-1] != 'X' && 
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
      j == k || i -2 >= 0 && dp[i-2][k-j] && s[i-1] != 'X') {
      ~~~~~~

• 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