oj.uz

답안 #198429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198429 2020-01-26T02:43:31 Z leonarda Lutrija (COCI19_lutrija) C++14
70 / 70
 459 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pi;
typedef long long int lint;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef set<int> si;
const int inf = 0x3f3f3f3f;
const int maxn = 0;
const int MOD = 1e9 + 7;

lint a, b;		
vector<lint> v;
vector<lint> ans;

bool isPrime (lint t)
{
	if(t == 0 or t == 1)
		return 0;
	for(lint i = 2; i <= sqrt(t); ++i)
		if(t % i == 0)
			return 0;
	return 1;
}

bool check (vector<lint> t)
{
	if(!isPrime(abs(a - t[0])))
		return 0;
	for(int i = 0; i < t.size() - 1; ++i)
		if(!isPrime(abs(t[i] - t[i + 1])))
			return 0;
	if(!isPrime(abs(t[t.size() - 1] - b)))
		return 0;
	return 1;
}

bool fuki (int x) 
{
	vector<lint> t;
	int i = 0;
	
	while(x) 
	{
		if(x % 2 == 1)
			t.pb(v[i]);
		x /= 2;
		++i;
	}
	
	sort(t.begin(), t.end());
	
	do
	{
		if(check(t))
		{
			ans.pb(a);
			for(int i = 0; i < t.size(); ++i)
				ans.pb(t[i]);
			ans.pb(b);
			return 1;
		}
			
	} while(next_permutation(t.begin(), t.end()));
	
	return 0;
}

bool solve (void)
{
	if(v.empty())
		return 0;
	
	for(int i = 1; i < pow(2, v.size()); ++i) 
		if(fuki(i))
			return 1;
			
	return 0;
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> a >> b;
	
	if(isPrime(abs(a - b)))
		return cout << 2 << endl << a << " " << b, 0;
	
	if(a != 2 and b != 2)
	{
		
		if(isPrime(a - 2))
			v.pb(a - 2);
		if(isPrime(a + 2))
			v.pb(a + 2);
		if(isPrime(b - 2))
			v.pb(b - 2);
		if(isPrime(b + 2))
			v.pb(b + 2);
		v.pb(2);		

		if(solve()) 
		{
			cout << ans.size() << endl;
			for(int i = 0; i < ans.size(); ++i)
				cout << ans[i] << " ";
		} else
			cout << -1;
	} else {
		if(a == 2) 
		{
			if(isPrime(b - 2))
				v.pb(b - 2);
			if(isPrime(b + 2))
				v.pb(b + 2);
		}
		if(b == 2)
		{
			if(isPrime(a - 2))
				v.pb(a - 2);
			if(isPrime(a + 2))
				v.pb(a + 2);
		}
		
		if(solve())
		{
			cout << ans.size() << endl;
			for(int i = 0; i < ans.size(); ++i)
				cout << ans[i] << " ";
		} else
			cout << -1;
	}

return 0;
}

Compilation message

lutrija.cpp: In function 'bool check(std::vector<long long int>)':
lutrija.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size() - 1; ++i)
                 ~~^~~~~~~~~~~~~~
lutrija.cpp: In function 'bool fuki(int)':
lutrija.cpp:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < t.size(); ++i)
                   ~~^~~~~~~~~~
lutrija.cpp: In function 'int main()':
lutrija.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < ans.size(); ++i)
                   ~~^~~~~~~~~~~~
lutrija.cpp:134:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < ans.size(); ++i)
                   ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 380 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 407 ms 380 KB Output is correct
2 Correct 104 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 376 KB Output is correct
2 Correct 103 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 459 ms 504 KB Output is correct
2 Correct 97 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 504 KB Output is correct
2 Correct 79 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct