제출 #333536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333536		shrek12357	Paint By Numbers (IOI16_paint)	C++14	100 / 100	483 ms	54284 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];
bool vis[MAXN][MAXK];

void backtrack(int i, int j) {
	if (vis[i][j]) {
		return;
	}
	vis[i][j] = true;
	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: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10