Submission #642559

#	Time	Username	Problem	Language	Result	Execution time	Memory
642559		ymm	Paint By Numbers (IOI16_paint)	C++17	0 / 100	0 ms	212 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 pos[K];
bool isx[N];
int next_[N];
vector<int> len;
int n, k;

pair<bool, int> place(int l, int x, int len)
{
	Loop (i,l,n-len+1) {
		if (next_[i] < i+len || isx[i+len]) {
			if (isx[i])
				return {false, i};
			else
				continue;
		}
		if (x < i+len)
			return {true, i};
	}
	return {false, -1};
}

int rem(int l)
{
	Loop (i,l,n)
		if (isx[i])
			return i;
	return -1;
}

string make_ans()
{
	string s(n, '_');
	Loop (i,0,k)
		Loop (j,pos[i],pos[i]+len[i])
			s[j] = 'X';
	return s;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
	n = s.size();
	k = c.size();
	len = c;
	next_[n] = N;
	LoopR (i,0,n) {
		next_[i] = s[i] == '_'? i: next_[i+1];
		isx[i] = s[i] == 'x' || s[i] == 'X';
	}
	int p = 0;
	int px = -1;
	for (;;) {
		if (p == k) {
			px = rem(pos[p]);
			if (px == -1)
				return make_ans();
			else
				--p;
		}
		bool suc; int val;
		tie(suc, val) = place(pos[p], px, c[p]);
		if (suc) {
			pos[p] = val;
			pos[p+1] = max(pos[p+1], val+c[p]+1);
			++p;
		} else {
			assert(px != -1);
			px = val;
			--p;
		}
	}
}

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