oj.uz

Submission #245276

# Submission time Handle Problem Language Result Execution time Memory
245276 2020-07-05T22:27:38 Z Ort Lutrija (COCI19_lutrija) C++11
70 / 70
 359 ms 504 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define mem(a, b) memset(a, (b), sizeof(a))
#define all(c) (c).begin(),(c).end()
#define sz(a) ((int)(a.size()))
#define ll long long
#define linf (ll)1e18
#define inf (int)1e9
#define minf 0x3F3F3F3F
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define mod 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 200005
#define watch(x) cerr<<#x<<" = "<<(x)<<endl;

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll a, b;
vector<ll> primes;

bool pr(ll x) {
  if(x<2) return 0;
  for(ll i=2;i*i<=x;i++) if(x%i==0) return 0;
  return 1;
}

bool pp(ll x, ll y) {return pr(abs(x-y));}

int main() {
	IO;
	cin >> a >> b;
	primes.pb(2);
	if(pr(a-2)) primes.pb(a-2);
	if(pr(a+2)) primes.pb(a+2);
	if(pr(b-2)) primes.pb(b-2);
	if(pr(b+2)) primes.pb(b+2);
	sort(primes.begin(),primes.end());
	primes.erase(remove(all(primes), a), primes.end());
	primes.erase(remove(all(primes), b), primes.end());
	for(int mask=0;mask<(1<<4);mask++) {
		vector<ll> subprimes;
		for(int i=0;i<sz(primes);i++) if(mask&(1<<i)) subprimes.pb(primes[i]);
		if(!sz(subprimes)) continue;
		do {
			bool ok = true;
			if(!pp(a,subprimes[0])) continue;
			if(!pp(b,subprimes[sz(subprimes)-1])) continue;
			for(int i=0;i<sz(subprimes)-1;i++) {
				if(!pp(subprimes[i],subprimes[i+1])) ok = false;
			}
			if(ok) {
				cout << sz(subprimes)+2 << "\n";
				cout << a << " ";
				for(int i=0;i<sz(subprimes);i++) cout << subprimes[i] << " ";
				cout << b << " ";
				return 0;
			}
  		} while (next_permutation(all(subprimes)));	
	}
	if(pp(a,b)) {
		cout << 2 <<  "\n";
		cout << a << " " << b;
		return 0;
	}
	cout << -1;
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 384 KB Output is correct
2 Correct 100 ms 384 KB Output is correct
3 Correct 196 ms 384 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 504 KB Output is correct
2 Correct 99 ms 384 KB Output is correct
3 Correct 142 ms 384 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 384 KB Output is correct
2 Correct 94 ms 384 KB Output is correct
3 Correct 136 ms 384 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 384 KB Output is correct
2 Correct 76 ms 384 KB Output is correct
3 Correct 51 ms 504 KB Output is correct