Submission #878903

#	Time	Username	Problem	Language	Result	Execution time	Memory
878903		Asymmetry	Paint By Numbers (IOI16_paint)	C++17	100 / 100	638 ms	182936 KiB

paint

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r)for(int i=(l);i<=(r);++i)
#define REP(i,n)FOR(i,0,(n)-1)
#define ssize(x)int(x.size())
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto&operator<<(auto&o,auto x){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

enum Cell {
	BLACK,
	WHITE,
	EMPTY
};
auto&operator<<(auto&o,Cell x) {
	return o<<int(x);
}

string solve_puzzle(string s, vector<int> c) {
	int n = ssize(s);
	int k = ssize(c);
	debug(n, k);
	debug(s);
	debug(c);
	auto calc = [&](vector<Cell> t) {
		vector dp(n + 1, vector(k + 1, 0));
		t.insert(t.begin(), EMPTY);
		t.emplace_back(EMPTY);
		debug("calc", t);
		vector<int> pref(n + 1), pref_black(n + 1);
		FOR (i, 1, n) {
			pref[i] = pref[i - 1] + (t[i] != WHITE);
			pref_black[i] = pref_black[i - 1] + (t[i] == BLACK);
		}
		debug(pref);
		dp[0][0] = 1;
		FOR (i, 1, n) {
			if (t[i] != BLACK)
				dp[i] = dp[i - 1];
			if (t[i] == WHITE)
				continue;
			if (c[0] <= i && (pref[i] - pref[i - c[0]]) == c[0] && pref_black[i - c[0]] == 0)
				dp[i][1] = 1;
			FOR (j, 1, k - 1)
				if (c[j] < i &&
						(pref[i] - pref[i - c[j]]) == c[j] &&
						t[i - c[j]] != BLACK)
					dp[i][j + 1] |= dp[i - c[j] - 1][j];
		}
		debug(dp);
		return dp;
	};
	vector<Cell> t(n);
	REP (i, n) {
		if (s[i] == 'X')
			t[i] = BLACK;
		if (s[i] == '_')
			t[i] = WHITE;
		if (s[i] == '.')
			t[i] = EMPTY;
	}
	auto pref = calc(t);
	reverse(c.begin(), c.end());
	auto suff = calc(vector(t.rbegin(), t.rend()));
	reverse(c.begin(), c.end());
	suff.emplace_back(suff.back());
	reverse(suff.begin(), suff.end());
	suff.emplace_back(suff.back());
	debug(pref);
	debug(suff);
	string ans = s;
	vector<int> can_be_white(n);
	FOR (i, 1, n)
		REP (j, k + 1)
			if (pref[i - 1][j] && suff[i + 1][k - j])
				can_be_white[i - 1] = 1;
	vector<int> can_be_black(n + 1);
	t.insert(t.begin(), EMPTY);
	t.emplace_back(EMPTY);
	vector sum(n + 1, 0), sum_black(n + 1, 0);
	FOR (i, 1, n) {
		sum[i] = sum[i - 1] + (t[i] != WHITE);
		sum_black[i] = sum_black[i - 1] + (t[i] == BLACK);
	}
	REP (j, k) {
		FOR (i, c[j], n) {
			if ((i == c[j]) && j)
				continue;
			if (j == 0) {
				/*
				if (j == k - 1) {
					if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[i - c[j]] == 0 && sum_black[n] == sum_black[i]) {
						debug("add", j, i, i - c[j], i);
						++can_be_black[i - c[j]];
						--can_be_black[i];
					}
				}
				else if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[i - c[j]] == 0 && t[i + 1] != BLACK && suff[i + 2][k - 1]) {
					debug("add", j, i, i - c[j], i);
					++can_be_black[i - c[j]];
					--can_be_black[i];
				}
				*/
				if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[i - c[j]] == 0 && t[i + 1] != BLACK && suff[i + 2][k - 1]) {
					debug("add", j, i, i - c[j], i);
					++can_be_black[i - c[j]];
					--can_be_black[i];
				}
			}
			else if (j == k - 1) {
				if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[n] == sum_black[i] && t[i - c[j]] != BLACK && pref[i - c[j] - 1][j]) {
					debug(j, i);
					++can_be_black[i - c[j]];
					--can_be_black[i];
				}
			}
			else {
				if ((sum[i] - sum[i - c[j]]) == c[j] && t[i - c[j]] != BLACK && t[i + 1] != BLACK && pref[i - c[j] - 1][j] && suff[i + 2][k - j - 1]) {
					debug(j, i);
					++can_be_black[i - c[j]];
					--can_be_black[i];
				}
			}
		}
	}
	FOR (i, 1, n - 1)
		can_be_black[i] += can_be_black[i - 1];
	REP (i, n) {
		if (t[i + 1] == BLACK)
			can_be_white[i] = 0;
		if (t[i + 1] == WHITE)
			can_be_black[i] = 0;
	}
	debug(can_be_black);
	debug(can_be_white);
	REP (i, n) {
		if (!can_be_black[i])
			ans[i] = '_';
		else if (!can_be_white[i])
			ans[i] = 'X';
		else
			ans[i] = '?';
	}
	return ans;
}

#ifdef LOCAL
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int k;
	cin >> k;
	vector<int> c(k);
	REP (i, k)
		cin >> c[i];
	string s;
	cin >> s;
	cout << solve_puzzle(s, c) << endl;
}
#endif

Compilation message (stderr)

paint.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto&operator<<(auto&o,Cell 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