oj.uz

Submission #631302

# Submission time Handle Problem Language Result Execution time Memory
631302 2022-08-18T02:59:07 Z SanguineChameleon Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 128 ms 50804 KB 
// BEGIN BOILERPLATE CODE

#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const int ms = 1e7 + 20;
const int inf = 1e9 + 20;
bool g[ms];
int pr[ms];
int p[ms];
int cc[ms];
int dp[ms];
int qz[ms];
int sz;

void just_do_it() {
	int n, q;
	cin >> n >> q;
	p[1] = 1;
	for (int i = 2; i < ms; i++) {
		if (!p[i]) {
			p[i] = i;
			pr[sz++] = i;
		}
		for (int j = 0; j < sz; j++) {
			if (i * pr[j] >= ms) {
				break;
			}
			p[i * pr[j]] = pr[j];
			if (i % pr[j] == 0) {
				break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		int d;
		cin >> d;
		g[d] = true;
	}
	cc[0] = n;
	int lt = 0;
	int rt = 0;
	for (int i = 1; i < 100; i++) {
		int f = -1;
		int x = i;
		while (x != 1) {
			if (p[x] != f) {
				f = p[x];
				if (g[f]) {
					cc[i]++;
					cc[i - p[x]]--;
				}
			}
			x /= p[x];
		}
		while (lt <= rt && !cc[qz[lt]]) {
			lt++;
		}
		if (lt > rt) {
			for (int j = i; j < ms; j++) {
				dp[j] = inf;
			}
			break;
		}
		else {
			dp[i] = dp[qz[lt]] + 1;
		}
		qz[++rt] = i;
	}
	for (int i = 0; i < q; i++) {
		int d;
		cin >> d;
		if (dp[d] == inf) {
			cout << "oo" << '\n';
		}
		else {
			cout << dp[d] << '\n';
		}
	}
}

// END MAIN CODE

Compilation message

brunhilda.cpp: In function 'void file_io(std::string, std::string)':
brunhilda.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 42060 KB Output isn't correct
2 Incorrect 106 ms 42040 KB Output isn't correct
3 Incorrect 105 ms 41976 KB Output isn't correct
4 Incorrect 106 ms 42076 KB Output isn't correct
5 Incorrect 108 ms 41972 KB Output isn't correct
6 Incorrect 111 ms 42080 KB Output isn't correct
7 Incorrect 112 ms 41980 KB Output isn't correct
8 Incorrect 128 ms 41976 KB Output isn't correct
9 Incorrect 113 ms 42068 KB Output isn't correct
10 Incorrect 111 ms 42048 KB Output isn't correct
11 Incorrect 106 ms 41976 KB Output isn't correct
12 Incorrect 104 ms 41976 KB Output isn't correct
13 Incorrect 108 ms 42016 KB Output isn't correct
14 Incorrect 111 ms 42080 KB Output isn't correct
15 Incorrect 101 ms 41996 KB Output isn't correct
16 Incorrect 104 ms 42044 KB Output isn't correct
17 Incorrect 109 ms 41972 KB Output isn't correct
18 Incorrect 110 ms 42196 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 42928 KB Output isn't correct
2 Incorrect 115 ms 50784 KB Output isn't correct
3 Incorrect 106 ms 42976 KB Output isn't correct
4 Incorrect 106 ms 42068 KB Output isn't correct
5 Incorrect 113 ms 43244 KB Output isn't correct
6 Incorrect 104 ms 42108 KB Output isn't correct
7 Incorrect 102 ms 42944 KB Output isn't correct
8 Incorrect 104 ms 42072 KB Output isn't correct
9 Incorrect 108 ms 43300 KB Output isn't correct
10 Incorrect 108 ms 42980 KB Output isn't correct
11 Incorrect 104 ms 42564 KB Output isn't correct
12 Incorrect 105 ms 42048 KB Output isn't correct
13 Incorrect 124 ms 42444 KB Output isn't correct
14 Incorrect 103 ms 42072 KB Output isn't correct
15 Incorrect 118 ms 42820 KB Output isn't correct
16 Incorrect 111 ms 50804 KB Output isn't correct
17 Incorrect 108 ms 42060 KB Output isn't correct
18 Incorrect 108 ms 43968 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 43084 KB Output isn't correct
2 Incorrect 118 ms 42844 KB Output isn't correct
3 Incorrect 112 ms 42804 KB Output isn't correct
4 Incorrect 122 ms 42416 KB Output isn't correct
5 Incorrect 127 ms 46548 KB Output isn't correct
6 Incorrect 123 ms 42432 KB Output isn't correct
7 Incorrect 117 ms 44352 KB Output isn't correct
8 Incorrect 115 ms 43108 KB Output isn't correct
9 Incorrect 112 ms 43124 KB Output isn't correct
10 Incorrect 108 ms 42240 KB Output isn't correct
11 Incorrect 110 ms 42264 KB Output isn't correct
12 Incorrect 109 ms 42304 KB Output isn't correct
13 Incorrect 116 ms 42576 KB Output isn't correct
14 Incorrect 114 ms 42272 KB Output isn't correct
15 Incorrect 116 ms 42356 KB Output isn't correct
16 Incorrect 108 ms 42160 KB Output isn't correct
17 Incorrect 110 ms 42908 KB Output isn't correct
18 Incorrect 114 ms 42964 KB Output isn't correct
19 Incorrect 110 ms 42804 KB Output isn't correct
20 Incorrect 113 ms 42896 KB Output isn't correct
21 Incorrect 122 ms 42284 KB Output isn't correct
22 Incorrect 125 ms 43720 KB Output isn't correct
23 Incorrect 119 ms 43188 KB Output isn't correct
24 Incorrect 122 ms 42420 KB Output isn't correct
25 Incorrect 121 ms 42348 KB Output isn't correct
26 Incorrect 121 ms 42412 KB Output isn't correct
27 Incorrect 117 ms 43428 KB Output isn't correct
28 Incorrect 118 ms 42284 KB Output isn't correct
29 Incorrect 125 ms 43668 KB Output isn't correct
30 Incorrect 121 ms 43176 KB Output isn't correct
31 Incorrect 119 ms 42612 KB Output isn't correct
32 Incorrect 120 ms 42344 KB Output isn't correct
33 Incorrect 124 ms 42528 KB Output isn't correct
34 Incorrect 117 ms 44428 KB Output isn't correct
35 Incorrect 119 ms 42312 KB Output isn't correct
36 Incorrect 127 ms 43768 KB Output isn't correct
37 Incorrect 126 ms 46612 KB Output isn't correct
38 Incorrect 123 ms 42472 KB Output isn't correct
39 Incorrect 121 ms 42392 KB Output isn't correct
40 Incorrect 120 ms 42444 KB Output isn't correct
41 Incorrect 117 ms 45428 KB Output isn't correct
42 Incorrect 117 ms 42288 KB Output isn't correct