Submission #828273

#	Time	Username	Problem	Language	Result	Execution time	Memory
828273		caganyanmaz	Paint By Numbers (IOI16_paint)	C++14	Compilation error	0 ms	0 KiB

paint

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

#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:6:10: fatal error: ../debug.h: No such file or directory
    6 | #include "../debug.h"
      |          ^~~~~~~~~~~~
compilation terminated.