Submission #147817

#	Time	Username	Problem	Language	Result	Execution time	Memory
147817		sensiel	Paint By Numbers (IOI16_paint)	C++11	Compilation error	0 ms	0 KiB

paint

#include <bits/stdc++.h>
using namespace std;


const int TAILLE_MAX = 200005;
const int MAX_SUITE = 105;

bool result_noir[TAILLE_MAX * 2];
bool result_blanc[TAILLE_MAX];
bool debut_blanc[TAILLE_MAX * 2];
bool occurence[TAILLE_MAX][MAX_SUITE];
bool dp[TAILLE_MAX][MAX_SUITE];
int suite[MAX_SUITE];
string patternDepart;

int nSuite;
int puissance = 1;
int taille;


//////////////TREE FUNCTIONS/////////////////

void trie(int index)
{
	if(index < puissance)
	{
		trie(index * 2);
		trie(index * 2 + 1);
		if(debut_blanc[index * 2] == true || debut_blanc[index * 2 + 1] == true)
		{
			debut_blanc[index] = true;
		}
	}
}

void treeInterInsert(int debutCouvert, int finCouvert, int debutInter, int finInter, int index)
{
	if(debutCouvert == debutInter && finCouvert == finInter)
	{
		result_noir[index] = true;
		return;
	}

	int mid = (debutCouvert+finCouvert)/2;

	if(debutInter > mid)
	{
		treeInterInsert(mid+1, finCouvert, debutInter,finInter, index * 2 + 1);
	}
	else if(finInter <= mid)
	{
		treeInterInsert(debutCouvert, mid, debutInter, finInter, index * 2);
	}
	else
	{
		treeInterInsert(debutCouvert, mid, debutInter, mid, index * 2);
		treeInterInsert(mid + 1, finCouvert, mid + 1, finInter, index * 2 + 1);
	}
}

bool SearchBlanc(int debutCouvert, int finCouvert, int debutInter, int finInter, int index)
{
	if(debutCouvert == debutInter && finCouvert == finInter)
	{
		return debut_blanc[index];
	}

	int mid = (debutCouvert+finCouvert)/2;

	if(debutInter > mid)
	{
		return SearchBlanc(mid+1, finCouvert, debutInter,finInter, index * 2 + 1);
	}
	else if(finInter <= mid)
	{
		return SearchBlanc(debutCouvert, mid, debutInter, finInter, index * 2);
	}
	else
	{
		bool gauche = SearchBlanc(debutCouvert, mid, debutInter, mid, index * 2);
		bool droite = SearchBlanc(mid + 1, finCouvert, mid + 1, finInter, index * 2 + 1);
		if(gauche == true || droite == true)
		{
			return true;
		}
		return false;
	}
}

//////////////////INIT FUNCTION/////////////////


void init()
{ 
	cin  >> patternDepart;
	cin >> nSuite;
	taille = patternDepart.length();

	while(puissance < taille)
	{
		puissance *= 2;
	}

	for(int iEmplacement = 0; iEmplacement < taille; iEmplacement++)
	{
		if(patternDepart[iEmplacement] == '_')
		{
			debut_blanc[puissance + iEmplacement] = true;
		}
	}
	trie(1);

	for(int iSuite = 0; iSuite < nSuite; iSuite++)
	{
		cin >> suite[iSuite];
	}
}

////////////////DP/////////////////////

bool dynaprog(int iEmplacement, int iProchainBloc)
{
	if(iEmplacement != -1)
	{
		occurence[iEmplacement][iProchainBloc] = true;
		if(patternDepart[iEmplacement] == 'X')
		{
			dp[iEmplacement][iProchainBloc] = false;
			return false;
		}
	}
	if(iEmplacement >= taille - 1)
	{
		if(iProchainBloc == nSuite)
		{
			dp[iEmplacement][iProchainBloc] = true;
			result_blanc[iEmplacement] = true;
			return true;
		}
		else
		{
			dp[iEmplacement][iProchainBloc] = false;
			return false;
		}
	}

	bool possible = false;

	if(occurence[iEmplacement + 1][iProchainBloc] == true)
	{
		if(dp[iEmplacement + 1][iProchainBloc] == true)
		{
			possible = true;
		}
	}
	else if(dynaprog(iEmplacement + 1, iProchainBloc) == true)
	{
		possible = true;
	}

	if(iEmplacement + suite[iProchainBloc]  < taille && iProchainBloc != nSuite)
	{
		if(SearchBlanc(1,puissance,iEmplacement + 2, iEmplacement + suite[iProchainBloc] + 1, 1) == false)
		{
			if(occurence[iEmplacement + suite[iProchainBloc] + 1][iProchainBloc + 1] == true)
			{
				if(dp[iEmplacement + suite[iProchainBloc] + 1][iProchainBloc + 1] == true)
				{
					treeInterInsert(1,puissance,iEmplacement + 2, iEmplacement + suite[iProchainBloc]+1, 1);
					possible = true;
				}
			}
			else if(dynaprog(iEmplacement + suite[iProchainBloc] + 1, iProchainBloc + 1) == true)
			{
				treeInterInsert(1,puissance,iEmplacement + 2, iEmplacement + suite[iProchainBloc]+ 1, 1);
				possible = true;
			}
		}
	}
	if(iEmplacement != -1)
	{
		if(possible == true)
		{
			result_blanc[iEmplacement] = true;
		}

		dp[iEmplacement][iProchainBloc] = possible;
	}
	return possible;
}


int main()
{
	init();
	dynaprog(-1,0);
	for(int iEmplacement = 0; iEmplacement < taille; iEmplacement++)
	{
		if(patternDepart[iEmplacement] != '.')
		{
			cout << patternDepart[iEmplacement];
		}
		else
		{
			bool blanc = result_blanc[iEmplacement];
			bool noir = false;
			int index = iEmplacement + puissance;
			while(index != 1)
			{
				if(result_noir[index] == true)
				{
					noir = true;
					break;
				}
				index = floor(index/2);
			}
			if(blanc == true && noir == true)
			{
				cout << '?';
			}
			else if(blanc == true)
			{
				cout << '_';
			}
			else
			{
				cout << 'X';
			}
		}
	}
}

Compilation message (stderr)

/tmp/ccaMYjcu.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccVhfJ62.o:paint.cpp:(.text.startup+0x0): first defined here
/tmp/ccaMYjcu.o: In function `main':
grader.cpp:(.text.startup+0x1eb): undefined reference to `solve_puzzle(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status