Submission #119970

#	Time	Username	Problem	Language	Result	Execution time	Memory
119970		Lawliet	Paint By Numbers (IOI16_paint)	C++14	10 / 100	238 ms	444 KiB

paint

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


#define MAX 110

using namespace std;

int N, K;

string ans;

vector<int> possibilities;

int bit(int v, int k)
{
	if(v & (1 << k)) return 1;
	return 0;
}

std::string solve_puzzle(string s, std::vector<int> c)
{
	N = s.size();
	K = c.size();

	ans.resize(N);

	for(int g = 0 ; g < (1 << N) ; g++)
	{
		int curBit = 0;

		vector<int> groups;

		//printf("--------------------------------------");

		//for(int h = N - 1 ; h >= 0 ; h--)
			//printf("%d ",bit(g , h)); 
		//printf("\n");

		while(curBit < N)
		{
			while(curBit < N && bit(g , curBit) == 0)
				curBit++;

			//printf("SAI %d\n",curBit);

			if(curBit == N) break;

			int cnt = 0;

			while(curBit < N && bit(g , curBit) == 1)
				curBit++, cnt++;

			//printf("cnt = %d\n",cnt);

			groups.push_back(cnt);
		}

		if(groups == c) possibilities.push_back(g);
	}

	int ansOR = 0;
	int ansAND = (1 << N) - 1;

	for(int g = 0 ; g < possibilities.size() ; g++)
	{
		//for(int h = N - 1 ; h >= 0 ; h--)
			//printf("%d ",bit(possibilities[g] , h));
		//printf("\n");
		ansOR = ansOR | possibilities[g];
		ansAND = ansAND & possibilities[g];
	}

	for(int g = 0 ; g < N ; g++)
	{
		if(bit(ansOR , g) == 1 && bit(ansAND , g) == 0) ans[g] = '?';
		else if(bit(ansOR , g) == 1) ans[g] = 'X';
		else ans[g] = '_';
	}

	return ans;
}

/*int main()
{
	string l;
	int cc;
	int n1;
	vector<int> ll;
	cin >> l;
	cin >> cc;

	for(int g = 0 ; g < cc ; g++)
	{
		scanf("%d",&n1);

		ll.push_back(n1);
	}

	printf("%s\n",solve_puzzle(l , ll).c_str());
}*/

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < possibilities.size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~

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