Submission #828274

#	Time	Username	Problem	Language	Result	Execution time	Memory
828274		caganyanmaz	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	312 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

using namespace std;

constexpr static int INF = 1e9;

struct SegTree
{
	vector<int> v;
	int n;
	SegTree(int n) : n(n), v(n*2, INF) {}
	void build(const vector<int>& r) { 
		for (int i = n; i < 2*n; i++) v[i] = r[i-n];
		for (int i = n-1; i > 0; i--) v[i] = min(v[i<<1], v[(i<<1)|1]);
	}
	int get(int l, int r)
	{
		int res = INF;
		for (l+=n,r+=n;l<r;l>>=1,r>>=1)
		{
			if (l&1) res = min(res, v[l++]);
			if (r&1) res = min(res, v[--r]);
		}
		return res;
	}
};

#include <cstdlib>

string solve_puzzle(string s, vector<int> c)
{
	vector<int> l(s.size()), r(s.size());
	SegTree st(c.size());
	st.build(c);
	int cc = 0;
	int cl = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (cc == c.size())
		{
			l[i] = c.size()*2;
			continue;
		}
		if (i - cl == c[cc])
		{
			for (int j = cl; j < i; j++)
				l[j] = cc*2+1;
			cc++;
			l[i] = cc*2;
			cl = i+1;
		}
		else if (s[i] == '_') 
		{
			while (cl <= i)
				l[cl++] = cc*2;
		}
	}

	if (cc < c.size())
	{
		for (int j = cl; j < s.size(); j++)
			l[j] = cc*2+1;
	}
	
	cc = c.size()-1;
	int cr = s.size();
	for (int i = s.size()-1; i >= 0; i--)
	{
		debug(i, cr, cc);
		if (cc < 0)
		{
			r[i] = 0;
			continue;
		}
		if (s[i] == '_') 
		{
			while (cr > i)
				r[--cr] = (cc+1) * 2;
		}
		else if (cr - i == c[cc])
		{
			for (int j = i; j < cr; j++)
				r[j] = cc*2+1;
			cc--;
			if (i > 0) r[i-1] = (cc+1)*2;
			cr = i-1;
			i--;
		}
	}
	vector<int> nlw(s.size());
	vector<int> nrw(s.size());
	int last = -1;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '_')
			last = i;
		nlw[i] = last;
	}
	last = s.size();
	for (int i = s.size()-1; i >= 0; i--)
	{
		if (s[i] == '_')
			last = i;
		nrw[i] = last;
	}
	string res(s.size(), '?');
	for (int i = 0; i < s.size(); i++)
	{
		if (l[i] != r[i]) 
		{
			int diff = nrw[i] - nlw[i];
			if (l[i]&1 != r[i]&1)
				continue;
			debug(i, nlw[i], nrw[i], diff, r[i]/2, l[i]/2, st.get(r[i]/2, l[i]/2));
			if (diff < st.get(r[i]/2, l[i]/2))
				res[i] = '_';
		}
		else if (l[i]&1) res[i] = 'X';
		else res[i] = '_';
	}
	debug(l,r);
	return res;
}

Compilation message (stderr)

paint.cpp: In constructor 'SegTree::SegTree(int)':
paint.cpp:17:6: warning: 'SegTree::n' will be initialized after [-Wreorder]
   17 |  int n;
      |      ^
paint.cpp:16:14: warning:   'std::vector<int> SegTree::v' [-Wreorder]
   16 |  vector<int> v;
      |              ^
paint.cpp:18:2: warning:   when initialized here [-Wreorder]
   18 |  SegTree(int n) : n(n), v(n*2, INF) {}
      |  ^~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
paint.cpp:46:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if (cc == c.size())
      |       ~~~^~~~~~~~~~~
paint.cpp:66:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  if (cc < c.size())
      |      ~~~^~~~~~~~~~
paint.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int j = cl; j < s.size(); j++)
      |                    ~~^~~~~~~~~~
paint.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
paint.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
paint.cpp:119:15: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  119 |    if (l[i]&1 != r[i]&1)

• 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