Submission #159565

#	Time	Username	Problem	Language	Result	Execution time	Memory
159565		Mounir	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1587 ms	94960 KiB

paint

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

const int LEN = 200 * 1000 + 1, CLUES = 101;

bool etatVerif[LEN][2];
bool visite[LEN][CLUES][2], possible[LEN][CLUES][2];
int cumul[LEN], nbCases;
int inter[LEN];


vector<int> indices;

bool estPossible(int idCase, int idClue, bool etat)
{
	if (idCase == -1 && idClue != 0)
		return false;
	if (idCase == -1)
		return true;
	
	if (visite[idCase][idClue][etat])
		return possible[idCase][idClue][etat];
	if (etatVerif[idCase][!etat])
		return false;
	if (etat && !idClue)
		return false;
	
	//Sinon, on doit vérifier que c'est possible seul comme un grand.
	//Si c'est un 1.
	if (etat)
	{
		int zoneInter = indices[idClue - 1];
		bool noProblem = (idCase  - zoneInter >= -1) && (cumul[idCase] == cumul[idCase - zoneInter + 1]);
		if (noProblem)
			possible[idCase][idClue][etat] = estPossible(idCase - zoneInter, idClue - 1, 0);
		if (possible[idCase][idClue][etat])
		{
			inter[idCase - zoneInter + 1] ++;
			inter[idCase + 1]--;
		}
	}
	else{
		possible[idCase][idClue][etat] = estPossible(idCase - 1, idClue, 0);
		possible[idCase][idClue][etat] |= estPossible(idCase - 1, idClue, 1);
	}
	visite[idCase][idClue][etat] = true;
	return possible[idCase][idClue][etat];
}

string resoudre()
{
	bool inutile = estPossible(nbCases-1,indices.size(),0);
	inutile = estPossible(nbCases-1,indices.size(),1);
	string chaine = "";
	
	int sumCur=  0;
	
	/*for (int i = 0; i < nbCases; ++i){
		for (int j = 0; j <= indices.size(); ++j)
			cout << possible[i][j][1] << " " ;
		cout << endl;
	}*/
	//cout << endl;	
	for (int idCara = 0; idCara < nbCases; ++ idCara)
	{
		sumCur += inter[idCara];
		//cout << sumCur << " ";
		bool is0, is1;
		
		if (!sumCur)
		{
		is1 = false;
		for (int i = 0; i <= (int)indices.size(); ++i)
			is1 |= (possible[idCara][i][1]);
		for (int i = 0; i <= (int)indices.size(); ++i)
			is1 &= !possible[idCara][i][0];
		
		is0 = false;
		for (int i = 0; i <= (int)indices.size(); ++i)
			is0 |= (possible[idCara][i][0]);
		for (int i = 0; i <= (int)indices.size(); ++i)
			is0 &= !possible[idCara][i][1];
		}
		else
		{
			is0 = false;
			is1 = true;
			for (int i = 0; i <= (int)indices.size(); ++i)
				is1 &= !possible[idCara][i][0];
		}
		if (is1)
			chaine += 'X';
		else if (is0)
			chaine += '_';
		else
			chaine += '?';
	}
	//cout << endl;
	return chaine;
}

void preprocess(string chaineIndice, vector<int> c)
{
	for (int idCara = 0; idCara < (int)chaineIndice.length(); ++ idCara)
	{
		if (chaineIndice[idCara] == 'X')
			etatVerif[idCara][1] = true;
		if (chaineIndice[idCara] == '_')
			etatVerif[idCara][0] = true;
		
		cumul[1 + idCara] = cumul[idCara] + etatVerif[idCara][0];
	}
	indices = c;
	nbCases = chaineIndice.length();
}

string solve_puzzle(string s, vector<int> c)
{
	preprocess(s, c);
	return resoudre();
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string resoudre()':
paint.cpp:52:7: warning: variable 'inutile' set but not used [-Wunused-but-set-variable]
  bool inutile = estPossible(nbCases-1,indices.size(),0);
       ^~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10