Submission #333535

#	Time	Username	Problem	Language	Result	Execution time	Memory
333535		shrek12357	Paint By Numbers (IOI16_paint)	C++14	10 / 100	2094 ms	384 KiB

paint

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
#include "paint.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0); 

const int MAXN = 2 * 1e5 + 5, MAXK = 105;

bool dp[MAXN][MAXK];
int preW[MAXN];
int preB[MAXN];
string s;
vector<int> c;

bool canX[MAXN], canY[MAXN];

void backtrack(int i, int j) {
	if (s[i] != 'X' && dp[i - 1][j]) {
		//dp[i][j] = dp[i - 1][j];
		backtrack(i - 1, j);
		canY[i] = true;
	}
	if (i - c[j] - 1 >= 0) {
		if (preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X' && dp[i - c[j] - 1][j - 1]) {
			//dp[i][j] |= dp[i - c[j] - 1][j - 1];
			backtrack(i - c[j] - 1, j - 1);
			for (int k = i - c[j] + 1; k <= i; k++) {
				canX[k] = true;
			}
			canY[i - c[j]] = true;
		}
	}
	if (i - c[j] == 0 && j == 1) {
		if (preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X') {
			//dp[i][j] = true;
			for (int k = i - c[j] + 1; k <= i; k++) {
				canX[k] = true;
			}
			canY[i - c[j]] = true;
		}
	}
}

string solve_puzzle(string S, vector<int> C) {
	s = S;
	c = C;
	int n = s.size();
	s = '*' + s;
	int m = c.size();
	c.insert(c.begin(), 0);
	for (int i = 1; i <= n; i++) {
		preW[i] = preW[i - 1];
		preB[i] = preB[i - 1];
		if (s[i] == '_') {
			preW[i]++;
		}
		if (s[i] == 'X') {
			preB[i]++;
		}
	}
	dp[0][0] = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if(s[i] != 'X')
				dp[i][j] = dp[i - 1][j];
			if (i - c[j] - 1 >= 0) {
				if(preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X')
					dp[i][j] |= dp[i - c[j] - 1][j - 1];
			}
			if (i - c[j] == 0 && j == 1) {
				if (preW[i] == preW[i - c[j]] && s[i - c[j]] != 'X')
					dp[i][j] = true;
			}
		}
	}
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	if (dp[n][m]) {
		backtrack(n, m);
	}
	string ans = "";
	for (int i = 1; i <= n; i++) {
		if (canX[i] && canY[i]) {
			ans += '?';
		}
		else if (canX[i]) {
			ans += 'X';
		}
		else {
			ans += '_';
		}
	}
	return ans;
}

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