Submission #465515

#	Time	Username	Problem	Language	Result	Execution time	Memory
465515		prvocislo	Sequence (BOI14_sequence)	C++17	100 / 100	207 ms	1092 KiB

sequence

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
typedef long long ll;
using namespace std;

ll solve(const vector<int>& v, bool not9)
{
	if (v.size() == 1)
	{
		ll ans = 0;
		for (int i = 1; i <= 9; i++) if (v[0] & (1 << i))
		{
			ans = ans * 10 + i;
			if (ans == i && (v[0] & 1)) ans *= 10;
		}
		if (!ans && (v[0] & 1)) ans = 10;
		return ans;
	}
	else
	{
		ll ans = 1e16;
		for (int last = 0; last <= 9 - (int)not9; last++)
		{
			vector<int> v2;
			int mask = 0;
			bool zero = false;
			for (int i = 0, j = last; i < v.size(); i++, j = (j + 1) % 10)
			{
				int my = v[i];
				if (my & (1 << j)) my ^= (1 << j);
				mask |= my;
				if (!j && (v[i] & 1)) zero = true;
				if (j == 9 || i + 1 == v.size())
				{
					v2.push_back(mask);
					mask = 0;
				}
			}
			ll num = solve(v2, (v.size() == 2 && last == 9)) * 10 + last;
			if (!num && zero) num = 10; // potrebujeme mat nieco na zaciatku, aby nam neodisla ta 0
			ans = min(ans, num);
		}
		return ans;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int k;
	cin >> k;
	vector<int> v(k);
	for (int i = 0; i < k; i++) cin >> v[i], v[i] = (1 << v[i]);
	cout << solve(v, false) << "\n";
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'll solve(const std::vector<int>&, bool)':
sequence.cpp:29:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |    for (int i = 0, j = last; i < v.size(); i++, j = (j + 1) % 10)
      |                              ~~^~~~~~~~~~
sequence.cpp:35:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if (j == 9 || i + 1 == v.size())
      |                   ~~~~~~^~~~~~~~~~~

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