oj.uz

Submission #631306

# Submission time Handle Problem Language Result Execution time Memory
631306 2022-08-18T03:02:52 Z SanguineChameleon Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 924 ms 168280 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 < ms; 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 81168 KB Output is correct
2 Correct 649 ms 159480 KB Output is correct
3 Correct 154 ms 83276 KB Output is correct
4 Correct 601 ms 159496 KB Output is correct
5 Correct 620 ms 159436 KB Output is correct
6 Correct 138 ms 81260 KB Output is correct
7 Correct 140 ms 83216 KB Output is correct
8 Correct 163 ms 88216 KB Output is correct
9 Correct 649 ms 159384 KB Output is correct
10 Correct 648 ms 159540 KB Output is correct
11 Correct 769 ms 159432 KB Output is correct
12 Correct 751 ms 159388 KB Output is correct
13 Correct 811 ms 159480 KB Output is correct
14 Correct 812 ms 159612 KB Output is correct
15 Correct 768 ms 159388 KB Output is correct
16 Correct 742 ms 159424 KB Output is correct
17 Correct 661 ms 159484 KB Output is correct
18 Correct 737 ms 159452 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 160256 KB Output is correct
2 Correct 699 ms 168280 KB Output is correct
3 Correct 825 ms 160412 KB Output is correct
4 Correct 762 ms 159464 KB Output is correct
5 Correct 924 ms 160656 KB Output is correct
6 Correct 717 ms 159472 KB Output is correct
7 Correct 740 ms 160348 KB Output is correct
8 Correct 813 ms 159508 KB Output is correct
9 Correct 904 ms 160656 KB Output is correct
10 Correct 797 ms 160348 KB Output is correct
11 Correct 788 ms 159864 KB Output is correct
12 Correct 783 ms 159424 KB Output is correct
13 Correct 736 ms 159852 KB Output is correct
14 Correct 852 ms 159532 KB Output is correct
15 Correct 887 ms 160236 KB Output is correct
16 Correct 727 ms 168212 KB Output is correct
17 Correct 841 ms 159404 KB Output is correct
18 Correct 879 ms 161368 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 160520 KB Output is correct
2 Correct 770 ms 160132 KB Output is correct
3 Correct 734 ms 160224 KB Output is correct
4 Correct 779 ms 159732 KB Output is correct
5 Correct 732 ms 163916 KB Output is correct
6 Correct 849 ms 159792 KB Output is correct
7 Correct 863 ms 161752 KB Output is correct
8 Correct 823 ms 160552 KB Output is correct
9 Correct 815 ms 160608 KB Output is correct
10 Correct 812 ms 159656 KB Output is correct
11 Correct 760 ms 159564 KB Output is correct
12 Correct 794 ms 159532 KB Output is correct
13 Correct 841 ms 160084 KB Output is correct
14 Correct 706 ms 160176 KB Output is correct
15 Correct 799 ms 159620 KB Output is correct
16 Correct 747 ms 159604 KB Output is correct
17 Correct 860 ms 160272 KB Output is correct
18 Correct 743 ms 160276 KB Output is correct
19 Correct 658 ms 160276 KB Output is correct
20 Correct 733 ms 160212 KB Output is correct
21 Correct 750 ms 160072 KB Output is correct
22 Correct 789 ms 161148 KB Output is correct
23 Correct 713 ms 160784 KB Output is correct
24 Correct 641 ms 159860 KB Output is correct
25 Correct 787 ms 159744 KB Output is correct
26 Correct 774 ms 159824 KB Output is correct
27 Correct 722 ms 160912 KB Output is correct
28 Correct 646 ms 159820 KB Output is correct
29 Correct 759 ms 161084 KB Output is correct
30 Correct 767 ms 160688 KB Output is correct
31 Correct 662 ms 159948 KB Output is correct
32 Correct 751 ms 159844 KB Output is correct
33 Correct 632 ms 159940 KB Output is correct
34 Correct 788 ms 161772 KB Output is correct
35 Correct 644 ms 159880 KB Output is correct
36 Correct 836 ms 161324 KB Output is correct
37 Correct 668 ms 163948 KB Output is correct
38 Correct 804 ms 159820 KB Output is correct
39 Correct 649 ms 159864 KB Output is correct
40 Correct 803 ms 159872 KB Output is correct
41 Correct 760 ms 162820 KB Output is correct
42 Correct 738 ms 159912 KB Output is correct