Submission #26468

#	Time	Username	Problem	Language	Result	Execution time	Memory
26468		zscoder	Sequence (BOI14_sequence)	C++14	0 / 100	36 ms	73936 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef long double ld;
typedef pair<int,int> ii;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

vi vec[100001];
int counter;

ll solve(int cnt)
{
	//cout << cnt << ' ' << vec[cnt].size() << endl;
	if(vec[cnt].size() > 1)
	{
		if(vec[cnt].size() == 2) cout << vec[cnt][0] << ' ' << vec[cnt][1] << endl;
		ll ans = ll(1e14);
		for(int d = 0; d < 10; d++)
		{
			//cout << cnt << ' ' << d << ' ' << ans << ' ' << vec[cnt].size() << endl;
			counter++;
			int tmp = d; int pos = 0;
			vec[counter].pb(0);
			for(int j = 0; j < vec[cnt].size(); j++)
			{
				if(tmp%10 == 0 && j != 0)
				{
					pos++;
					vec[counter].pb(0);
					int tmp2;
					int reqdig = vec[cnt][j];
					int digit = tmp%10;
					if(!((1<<digit)&reqdig)) tmp2 = (1<<digit);
					else tmp2 = 0;
					vec[counter][pos] |= tmp2;
				}
				else
				{
					int tmp2;
					int reqdig = vec[cnt][j];
					int digit = tmp%10;
					if(!((1<<digit)&reqdig)) tmp2 = (1<<digit);
					else tmp2 = 0;
					vec[counter][pos] |= tmp2;
				}
				tmp++;
			}
			ll val = solve(counter);
			ans = min(ans, val*10 + d);
		//	cout << cnt << ' ' << d << ' ' << ans << ' ' << vec[cnt].size() << endl;
		}
		return ans;
	}
	else if(vec[cnt].size() == 1)
	{
		int bit = vec[cnt][0];
		vi needed;
		for(int i = 0; i < 10; i++)
		{
			if(bit & (1<<i)) needed.pb(i);
		}
		if(needed.empty()) return 0;
		else if(needed.size() == 1 && needed[0] == 0) return 10;
		else
		{
			sort(needed.begin(), needed.end());
			ll retvalue = 0; ll power = 1;
			if(needed[0] == 0)
			{
				for(int i = int(needed.size()) - 1; i > 1; i--)
				{
					retvalue += needed[i]*power;
					power *= 10;
				}
				power *= 10;
				retvalue += needed[1]*power;
			}
			else
			{
				for(int i = int(needed.size()) - 1; i >= 0; i--)
				{
					retvalue += needed[i]*power;
					power *= 10;
				}
			}
			return retvalue;
		}
	}
	else
	{
		/*
		int d1 = vec[cnt][0];
		int d2 = vec[cnt][1];
		if((d2 - 1 == d1) || (d1 == 9 && d2 == 0))
		{
			if(d1 == 0) return 10;
			else return d1;
		}
		else if(d1 != 0 && d2 != 0)
		{
			if(d1 > d2) //d2*10 + d1, d2*10 + d1 + 1
			{
				if(d1 < 9)
				{
					return d2*10 + d1;
				}
				else
				{
					return d1*10 + d2 - 1;
				}
			}
			else //d1*10 + d2 - 1, d1*10 + d2;
			{
				return d1*10 + d2 - 1;
			}
		}
		else if(d1 == 0 && d2 == 0)
		{
			return 100;
		}
		else if(d1 == 0)
		{
			return d2*10;
		}
		else if(d2 == 0)
		{
			return d1*10;
		}
		*/
		
	}
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	//freopen("sequence.in", "r", stdin);
	int k;
	cin >> k;
	for(int i = 0; i < k; i++)
	{
		int x; cin >> x;
		vec[0].pb(x);
	}
	cout << solve(0) << '\n';
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'll solve(int)':
sequence.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < vec[cnt].size(); j++)
                     ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 33
• Subtask 3: 0 / 25
• Subtask 4: 0 / 33