Submission #43153

#	Time	Username	Problem	Language	Result	Execution time	Memory
43153		MatheusLealV	Paint By Numbers (IOI16_paint)	C++14	59 / 100	4 ms	1468 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], qtd[N], forb[N];

char v[N];

vector<int> pos[K], pos2[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);
		}
	}
}

void count()
{
	for(int p = 1; p <= n; p++)
	{
		if(v[p] != 'X') continue;

		int id;

		for(int i = 1; i <= k; i++)
		{
			bool can = false;

			for(auto x: pos[i])
			{
				if(x <= p && p < x + sz[i])
				{
					can = true;

					id = i;
				}
			}

			if(can) qtd[p] ++;
		}

		if(qtd[p] == 1)
		{
			forb[id] = 1;

			for(auto x: pos[id])
			{
				if(x <= p && p < x + sz[id])
				{
					pos2[id].push_back(x);
				}
			}
		}
	}
}

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();

	count();

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

		int tam = 0;

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

			tam = pos[i].size();
		}
		else
		{
			for(auto p: pos2[i])
				for(int j = p; j < p + sz[i]; j++) global[j] ++, cnt[j] ++;

			tam = pos2[i].size();
		}

		for(int j = 1; j <= n; j++) if(cnt[j] == tam) 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