제출 #104138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104138		hugo_pm	Paint By Numbers (IOI16_paint)	C++17	100 / 100	676 ms	201336 KiB

paint

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

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const int INF = (int)(1e9);

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxLen = 200005;
const int maxBlocs = 105;

const int BOTH=0, ON=1, OFF=2;
int info[maxLen];
int rep[maxLen];

int lenJeu, nbBlocs;
vector<int> blocs;

bool dp[2][maxBlocs][maxLen];
int gl[3][maxLen];

int drap[maxBlocs][maxLen];
int prdrap[maxBlocs][maxLen];

void proc(int mode, int blocsPris, int elemPris)
{
	bool &ans = dp[mode][blocsPris][elemPris];
	int curElem = elemPris-1;
	int curBloc = blocsPris-1;

	if (blocsPris == 0) {
		if (elemPris == 0) ans = true;
		else if (info[curElem] == ON) ans = false;
		else ans = dp[mode][blocsPris][elemPris-1];
		return;
	}

	if (elemPris == 0) {
		ans = false;
		return;
	}

	ans = false;
	int debPoseIci = curElem - blocs[curBloc] + 1;
	if (debPoseIci > gl[OFF][curElem]) { // Peut poser un bloc finissant en curElem
		bool ww = false;
		if (debPoseIci == 0) ww = (blocsPris == 1);
		else ww = (info[debPoseIci-1] != ON && dp[mode][blocsPris-1][debPoseIci-1]);
		bool w2 = ww;
		if (debPoseIci > 0) w2 = (ww && info[debPoseIci-1] != ON);
		if (mode == 0 && w2) drap[curBloc][curElem] = 1;
		ans |= ww;
	}
	if (info[curElem] != ON) {
		ans |= dp[mode][blocsPris][elemPris-1];
	}
}

bool tmp[maxLen][maxBlocs];

void comp(int mode)
{
	form(mode, 3) {
		int lst = -1;
		form(i, lenJeu) {
			if (info[i] == mode) lst = i;
			gl[mode][i] = lst;
		}
	}
	form(i, nbBlocs+1) {
		form(j, lenJeu+1) {
			proc(mode, i, j);
		}
	}
}

void doubleComp()
{
	comp(0);
	reverse(info, info+lenJeu);
	reverse(blocs.begin(), blocs.end());
	comp(1);
	reverse(info, info+lenJeu);
	reverse(blocs.begin(), blocs.end());

}

bool canOFF(int indElem)
{
	if (info[indElem] == ON) return false;
	form(blocsGauche, nbBlocs+1) {
		int blocsDroite = nbBlocs - blocsGauche;
		int rev = lenJeu - (indElem+1);
		if (dp[0][blocsGauche][indElem] && dp[1][blocsDroite][rev]) return true;
	}
	return false;
}

bool canON(int indElem) {
	if (info[indElem] == OFF) return false;
	form(curBloc, nbBlocs) {
		int sz = blocs[curBloc];
		int dt = indElem, ft = min(indElem+sz-1, lenJeu-1);
		int cc = prdrap[curBloc][ft];
		if (dt) cc -= prdrap[curBloc][dt-1];
		if (cc > 0) return true;
	}
	return false;
}

void solve()
{
	doubleComp();

	form(i, nbBlocs) {
		form(j, lenJeu) if (drap[i][j]) {
			int rstBloc = nbBlocs-(i+1);
			int rstElem = lenJeu-(j+1);
			bool ww = false;
			if (rstElem == 0) ww = (rstBloc == 0);
			else if (rstBloc == 0) ww = dp[1][rstBloc][rstElem];
			else ww = (info[j+1] != ON && dp[1][rstBloc][rstElem-1]);
			if (!ww) drap[i][j] = 0;
		}
	}
	form(i, nbBlocs) {
		prdrap[i][0] = drap[i][0];
		form2(j, 1, lenJeu) {
			prdrap[i][j] = prdrap[i][j-1] + drap[i][j];
		}
	}


	form(i, lenJeu) {
		bool cal = canON(i), cet = canOFF(i);
		assert(cal || cet);
		if (cal && cet) rep[i] = BOTH;
		else if (cal) rep[i] = ON;
		else if (cet) rep[i] = OFF;
	}
}

string solve_puzzle(std::string s, std::vector<int> c) {
	lenJeu = s.length();
	nbBlocs = c.size();
	blocs = c;

	form(i, lenJeu) {
		if (s[i] == '.') info[i] = BOTH;
		else if (s[i] == 'X') info[i] = ON;
		else info[i] = OFF;
	}
	solve();
	form(i, lenJeu) {
		if (rep[i] == BOTH) s[i] = '?';
		else if (rep[i] == ON) s[i] = 'X';
		else s[i] = '_';	
	}
	return s;
}

• 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