Submission #599179

#	Time	Username	Problem	Language	Result	Execution time	Memory
599179		8e7	Paint By Numbers (IOI16_paint)	C++17	100 / 100	529 ms	9524 KiB

paint

//Challenge: Accepted
#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1e9;
int cnt[2][maxn];
int zero[maxn], one[maxn];
string solve_puzzle(string s, vector<int> c) {
	int n = s.size(), m = c.size();
	vector<vector<bool> > pref(m+1, vector<bool>(n+1, 0)), suf(m+1, vector<bool>(n+1, 0));
	for (int i = 0;i < n;i++) {
		if (s[i] == '_') cnt[0][i] = 1;
		else if (s[i] == 'X') cnt[1][i] = 1;
		if (i) cnt[0][i] += cnt[0][i-1], cnt[1][i] += cnt[1][i-1];
	}
	auto getcnt = [&] (int b, int l, int r){
		return cnt[b][r] - (l ? cnt[b][l-1] : 0);		
	};
	suf[0][n] = 1;	
	for (int i = n - 1;i >= 0;i--) {
		for (int j = 0;j <= m;j++) {
			if (j) {
				int r = i + c[m-j] - 1;
				if (r < n && getcnt(0, i, r) == 0) {
					if (r == n-1){
						suf[j][i] = j == 1;
					} else if (s[r+1] != 'X'){
						suf[j][i] = suf[j][i] | suf[j-1][r+2];
						
					}
				}
			}
			if (s[i] != 'X') suf[j][i] = suf[j][i] | suf[j][i+1];
		}
	}
	debug("zisk");
	for (int i = 0;i < n;i++) {
		for (int j = 0;j <= m;j++) {
			if (j) {
				int l = i - c[j-1] + 1;
				if (l >= 0 && getcnt(0, l, i) == 0) {
					if (l == 0) {
						pref[j][i] = j == 1;
					} else if (l == 1) {
						pref[j][i] = (j == 1) && (s[0] != 'X');
					} else if (s[l-1] != 'X'){
						pref[j][i] = pref[j][i] | pref[j-1][l-2];
					}
					if (pref[j][i] && (i >= n-1 || s[i+1] != 'X') && ((i == n-1 && j == m) || suf[m-j][i+2])) {
						one[l]++, one[i+1]--;		
					}
					if (pref[j][i]) debug(j, l, i);
				}
			}
			if (s[i] != 'X') {
				if (i) pref[j][i] = pref[j][i] | pref[j][i-1];
				else if (j == 0) pref[j][i] = 1;
			}
			bool le = ((i == 0 && j == 0) || (i != 0 && pref[j][i-1]));
			bool ri = ((i == n - 1 && j == m) || (i < n - 1 && suf[m-j][i+1]));
			if (le && ri) zero[i] = 1;	
		}
	}
	for (int i = 1;i < n;i++) one[i] += one[i-1];	
	string ans;
	for (int i = 0;i < n;i++) {
		if (s[i] == 'X') zero[i] = 0;
		else if (s[i] == '_') one[i] = 0;
		if (!one[i]) ans += "_";
		else if (!zero[i])ans += "X";
		else ans += "?";
	}
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
paint.cpp:52:2: note: in expansion of macro 'debug'
   52 |  debug("zisk");
      |  ^~~~~
paint.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
paint.cpp:68:22: note: in expansion of macro 'debug'
   68 |      if (pref[j][i]) debug(j, l, i);
      |                      ^~~~~

• 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