제출 #343966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343966		LucaDantas	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2089 ms	109676 KiB

paint

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

#define sz(a) (int)((a).size())
#define pb push_back

constexpr int maxn = 2e5+10, maxk = 110;

int dir[maxn], dp[maxn][maxk], mark[maxn], n;
string s;
vector<int> c;

struct SegmentTree
{
	int tree[4*maxn];
	void upd(int node, int i, int j, int l, int r) {
		if(i > r || j < l || tree[node]) return;
		if(i >= l && j <= r) return (void)(tree[node] = 1);
		int m = (i+j) >> 1;
		upd(2*node, i, m, l, r); upd(2*node+1, m+1, j, l, r);
	}
	bool query(int node, int i, int j, int pos) {
		if(i == j || tree[node]) return tree[node];
		int m = (i+j) >> 1;
		if(pos <= m) return query(2*node, i, m, pos);
		return query(2*node+1, m+1, j, pos);
	}
} seg;

bool solve(int pos, int j) {
	if(dp[pos][j] != -1) return dp[pos][j];
	if(pos >= n) return j == sz(c);
	dp[pos][j] = 0;
	if(j < sz(c) && pos + c[j] - 1 < dir[pos] && s[pos+c[j]] != 'X' && solve(pos + c[j] + 1, j+1))
		seg.upd(1, 0, n-1, pos, pos + c[j] - 1), mark[pos+c[j]] = 1, dp[pos][j] = 1;
	if(s[pos] != 'X' && solve(pos+1, j))
		mark[pos] = 1, dp[pos][j] = 1;
	return dp[pos][j];
}

string solve_puzzle(string S, vector<int> C) {
	s = S; c = C;
	n = sz(s);
	dir[n] = n;
	for(int i = n-1; i >= 0; i--) {
		dir[i] = dir[i+1];
		if(s[i] == '_')
			dir[i] = i;
	}
	for(int i = 0; i < maxn; i++)
		for(int j = 0; j < maxk; j++)
			dp[i][j] = -1;
	solve(0, 0);
	string ans;
	for(int i = 0; i < n; i++) {
		if(seg.query(1, 0, n-1, i) && mark[i]) ans.pb('?');
		else if(mark[i]) ans.pb('_');
		else ans.pb('X');
	}
	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: 0 / 10