Submission #43152

#	Time	Username	Problem	Language	Result	Execution time	Memory
43152		MatheusLealV	Paint By Numbers (IOI16_paint)	C++14	59 / 100	4 ms	1492 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] == pos[i].size()) 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;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:92:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; j <= n; j++) if(cnt[j] == pos[i].size()) ans[j - 1] = 'X';
                                         ^

• 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