oj.uz

답안 #465492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465492 2021-08-16T08:37:18 Z prvocislo 수열 (BOI14_sequence) C++17
25 / 100
 154 ms 972 KB 
#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));
			if (!num && zero) num = 1; // potrebujeme mat nieco na zaciatku, aby nam neodisla ta 0
			num = num * 10 + last;
			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

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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 16 ms 392 KB Output is correct
3 Correct 21 ms 332 KB Output is correct
4 Correct 17 ms 332 KB Output is correct
5 Correct 15 ms 324 KB Output is correct
6 Correct 19 ms 332 KB Output is correct
7 Correct 101 ms 708 KB Output is correct
8 Correct 66 ms 588 KB Output is correct
9 Correct 154 ms 972 KB Output is correct
10 Correct 138 ms 912 KB Output is correct

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -