Submission #361405

#	Time	Username	Problem	Language	Result	Execution time	Memory
361405		NachoLibre	Paint By Numbers (IOI16_paint)	C++17	100 / 100	541 ms	140324 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "paint.h"
#else
#endif

string solve_puzzle(string s, vector<int> c) {
	int n = s.size();
	int m = c.size();
	s = " " + s + " ";
	{
		vector<int> t = c;
		c.clear();
		c.push_back(0);
		for(int i = 0; i < (int)t.size(); ++i)
			c.push_back(t[i]);
		c.push_back(0);
	}
	bool cu[2][m + 2][n + 2];
	int qt[n + 2] = {0};
	qt[n + 1] = 0;
	for(int i = 1; i <= n; ++i) {
		qt[i] = qt[i - 1] + (s[i] == '_');
	}
	cu[0][0][0] = 1;
	for(int i = 1; i <= m; ++i) cu[0][i][0] = 0;
	for(int i = 1; i <= n; ++i) cu[0][0][i] = (cu[0][0][i - 1] && (s[i] != 'X'));
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			cu[0][i][j] = 0;
			if(s[j] == '_') {
				cu[0][i][j] = cu[0][i][j - 1];
			} else if(s[j] == 'X') {
				if(c[i] <= j && qt[j] == qt[j - c[i]] && s[j - c[i]] != 'X') {
					if(c[i] < j) cu[0][i][j] |= cu[0][i - 1][j - c[i] - 1];
					else cu[0][i][j] |= (i == 1);
				}
			} else {
				cu[0][i][j] = cu[0][i][j - 1];
				if(c[i] <= j && qt[j] == qt[j - c[i]] && s[j - c[i]] != 'X') {
					if(c[i] < j) cu[0][i][j] |= cu[0][i - 1][j - c[i] - 1];
					else cu[0][i][j] |= (i == 1);
				}
			}
		}
	}
	//  //  //  //  //  //  //  //
	for(int i = n; i >= 1; --i)
		qt[i] = qt[i + 1] + (s[i] == '_');
	cu[1][m + 1][n + 1] = 1;
	for(int i = 1; i <= m; ++i) cu[1][i][n + 1] = 0;
	for(int i = n; i >= 1; --i) cu[1][m + 1][i] = (cu[1][m + 1][i + 1] && (s[i] != 'X'));
	for(int i = m; i >= 1; --i) {
		for(int j = n; j >= 1; --j) {
			cu[1][i][j] = 0;
			if(s[j] == '_') {
				cu[1][i][j] = cu[1][i][j + 1];
			} else if(s[j] == 'X') {
				if(c[i] <= n - j + 1 && qt[j] == qt[j + c[i]] && s[j + c[i]] != 'X') {
					if(c[i] < n - j + 1) cu[1][i][j] |= cu[1][i + 1][j + c[i] + 1];
					else cu[1][i][j] |= (i == m);
				}
			} else {
				cu[1][i][j] = cu[1][i][j + 1];
				if(c[i] <= n - j + 1 && qt[j] == qt[j + c[i]] && s[j + c[i]] != 'X') {
					if(c[i] < n - j + 1) cu[1][i][j] |= cu[1][i + 1][j + c[i] + 1];
					else cu[1][i][j] |= (i == m);
				}
			}
		}
	}
	//  //  //  //  //  //  //  //
	for(int i = 1; i <= n; ++i)
		qt[i] = qt[i - 1] + (s[i] == '_');
	bool cm[m + 2][n + 2];
	for(int i = 1; i <= n; ++i)
		cm[0][i] = 0;
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			cm[i][j] = 0;
			if(c[i] <= j && qt[j] == qt[j - c[i]] && s[j - c[i]] != 'X') {
				if(c[i] < j) cm[i][j] |= cu[0][i - 1][j - c[i] - 1];
				else cm[i][j] |= (i == 1);
			}
		}
	}
	//  //  //  //  //  //  //  //
	int fl[m + 2][n + 2];
	for(int i = 1; i <= m; ++i) {
		fl[i][0] = 0;
		for(int j = 1; j <= n; ++j) {
			if(s[j + 1] != 'X') {
				if(j < n) fl[i][j] = (cm[i][j] && cu[1][i + 1][j + 2]);
				else fl[i][j] = (cm[i][j] && i == m);
			} else {
				fl[i][j] = 0;
			}
			fl[i][j] += fl[i][j - 1];
		}
		fl[i][n + 1] = fl[i][n];
	}
	//  //  //  //  //  //  //  //
	bool gm[n + 2][2];
	for(int j = 1; j <= n; ++j) {
		gm[j][0] = gm[j][1] = 0;
		if(s[j] != '.') continue;
		for(int i = 0; i <= m; ++i) {
			if(cu[0][i][j - 1] && cu[1][i + 1][j + 1]) {
				gm[j][0] |= 1;
			}
			if(i) {
				int x = j + c[i] - 1;
				if(x > n) x = n;
				gm[j][1] |= (fl[i][j - 1] != fl[i][x]);
			}
		}
	}
	//  //  //  //  //  //  //  //
	string dr = "";
	for(int j = 1; j <= n; ++j) {
		if(s[j] != '.') dr += s[j];
		else {
			if(gm[j][0] && gm[j][1]) dr += '?';
			else if(gm[j][0]) dr += '_';
			else dr += 'X';
		}
	}
	//  //  //  //  //  //  //  //
	#ifdef wambule
	for(int i = 0; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			cout << cu[0][i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for(int i = m + 1; i >= 1; --i) {
		for(int j = 1; j <= n; ++j) {
			cout << cu[1][i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			cout << cm[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			cout << fl[i][j] - fl[i][j - 1] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for(int i = 0; i < 2; ++i) {
		for(int j = 1; j <= n; ++j) {
			cout << gm[j][i] << " ";
		}
		cout << endl;
	}
	cout << endl;
	#endif
	return dr;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s = solve_puzzle(".X........", {3});
	cout << s << endl;
	return 0;
}
#endif

• 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