Submission #642576

#	Time	Username	Problem	Language	Result	Execution time	Memory
642576		ymm	Paint By Numbers (IOI16_paint)	C++17	100 / 100	456 ms	46892 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200010;
const int K = 110;
int next_[N];
bool isx[N];
bool dp1[N][K], dp2[N][K];
int canx[N];
int can_[N];
int n, k;

vector<int> c;

bool can(int i, int j, bool l, bool r)
{
	int len = c[j];
	if (i < 0)
		return 0;
	if (i + len > n)
		return 0;
	if (next_[i] < i + len)
		return 0;
	if (l && i != 0 && isx[i-1])
		return 0;
	if (r && i + len != n && isx[i + len])
		return 0;
	return 1;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
	n = s.size();
	k = c.size();
	::c = c;
	next_[n] = N;
	LoopR (i,0,n) {
		next_[i] = s[i] == '_'? i: next_[i+1];
		isx[i] = s[i] == 'x' || s[i] == 'X';
	}
	dp1[0][0] = 1;
	Loop (i,1,n+1) {
		dp1[i][0] = !isx[i-1] && dp1[i-1][0];
		Loop (j,0,k) {
			dp1[i][j+1] |= can(i-c[j], j, 1, 0) && dp1[i - c[j] - (i-c[j]>0)][j];
			dp1[i][j+1] |= !isx[i-1] && dp1[i-1][j+1];
		}
	}
	dp2[n][k] = 1;
	LoopR (i,0,n) {
		dp2[i][k] = !isx[i] && dp2[i+1][k];
		Loop (j,0,k) {
			dp2[i][j] |= can(i, j, 0, 1) && dp2[i + c[j] + (i+c[j]<n)][j+1];
			dp2[i][j] |= !isx[i] && dp2[i+1][j];
		}
	}
	Loop (i,0,n)
		Loop (j,0,k+1)
			can_[i] |= dp1[i][j] && dp2[i+1][j] && !isx[i];
	Loop (j,0,k) {
		Loop (i,0,n-c[j]+1) {
			int tmp = can(i, j, 1, 1) && dp1[i - (i>0)][j] && dp2[i + c[j] + (i+c[j]<n)][j+1];
			canx[i     ] += tmp;
			canx[i+c[j]] -= tmp;
		}
	}
	Loop (i,0,n)
		canx[i+1] += canx[i];
	string ans(n, '.');
	Loop (i,0,n) {
		     if (canx[i] && can_[i]) s[i] = '?';
		else if (canx[i]           ) s[i] = 'X';
		else if (           can_[i]) s[i] = '_';
		else                         assert(false);
	}
	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