Submission #43091

#	Time	Username	Problem	Language	Result	Execution time	Memory
43091		MatheusLealV	Paint By Numbers (IOI16_paint)	C++14	59 / 100	4 ms	1520 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define K 120
#define N 200050
using namespace std;

int ini[K], fim[K], n, k, sz[K], cnt[N], global[N];

string ans;

int sum[N];

char v[N];

vector<int> pos[K];

void get_position()
{
	for(int i = 1; i <= k; i++)
	{
		int st = ini[i - 1] + sz[i - 1] + 1;

		while(true)
		{
			int en = st + sz[i] - 1;

			if(sum[en] - sum[st - 1] > 0) st ++;

			else break;
		}

		ini[i] = st;
	}

	fim[k + 1] = n + 2;

	for(int i = k; i >= 1; i--)
	{
		int st = fim[i + 1] - sz[i] - 1;

		while(true)
		{
			int en = st + sz[i] - 1;

			if(sum[en] - sum[st - 1] > 0) st --;

			else break;
		}

		fim[i] = st;
	}

	for(int i = 1; i <= k; i++)
	{
		for(int st = ini[i]; st <= fim[i]; st++)
		{
			int en = st + sz[i] - 1;

			if(!(sum[en] - sum[st - 1])) pos[i].push_back(st);
		}
	}
}

string solve_puzzle(string s, vector<int> c)
{
	n = s.size();

	string ans = s;

	k = c.size();

	for(int i = 0; i < n ; i++)
	{
		v[i + 1] = s[i];

		if(s[i] == '_') sum[i + 1] ++;
	}

	for(int i = 1; i <= n; i++) sum[i] += sum[i - 1];

	for(int i = 1; i <= k; i++) sz[i] = c[i - 1];

	get_position();

	for(int i = 1; i <= k; i++)
	{
		memset(cnt, 0, sizeof cnt);

		for(auto p: pos[i])
			for(int j = p; j < p + sz[i]; j++) global[j] ++, cnt[j] ++;

		for(int j = 1; j <= n; j++) if(cnt[j] == fim[i] - ini[i] + 1) ans[j - 1] = 'X';
	}

	for(int i = 1; i <= n; i++)
	{
		if(!global[i] && ans[i - 1] != 'X') ans[i - 1] = '_';

		else if(ans[i - 1] == '.') ans[i - 1] = '?';
	}

	return ans;
}

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