Submission #200612

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
200612	2020-02-07T15:27:20 Z	Sorting	Strongbox (POI11_sej)	C++14	100 / 100	440 ms	6776 KB

#include <bits/stdc++.h>

using namespace std;

vector<long long > m, primes;
long long ans;

set<long long> visited;

void dfs(long long num, bool check){
	visited.insert(num);
	if(check)
		ans = min(ans, num);

	for(long long prime: primes)
		if(num % prime == 0 && !visited.count(num / prime))
			dfs(num / prime, check);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	long long n, k;
	cin >> n >> k;
	ans = n;

	m.resize(k);
	for(int i = 0; i < k; ++i)
		cin >> m[i];
	
	long long n_copy = n;
	for(long long d = 2; d * d <= n_copy; ++d){
		if(n_copy % d == 0){
			primes.push_back(d);
			while(n_copy % d == 0)
				n_copy /= d;
		}
	}
	if(n_copy > 1)
		primes.push_back(n_copy);

	for(int i = 0; i < k; ++i){
		dfs(__gcd(n, m[i]), i == k - 1);
	}

	cout << n / ans << "\n";
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	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

Subtask #4
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	380 KB	Output is correct
3	Correct	7 ms	376 KB	Output is correct

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	376 KB	Output is correct
2	Correct	6 ms	376 KB	Output is correct
3	Correct	15 ms	376 KB	Output is correct
4	Correct	11 ms	632 KB	Output is correct

Subtask #6
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	23 ms	1016 KB	Output is correct
3	Correct	105 ms	376 KB	Output is correct
4	Correct	22 ms	1016 KB	Output is correct

Subtask #7
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	376 KB	Output is correct
2	Correct	6 ms	376 KB	Output is correct
3	Correct	109 ms	376 KB	Output is correct
4	Correct	20 ms	1016 KB	Output is correct

Subtask #8
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	376 KB	Output is correct
2	Correct	22 ms	1144 KB	Output is correct
3	Correct	77 ms	380 KB	Output is correct
4	Correct	21 ms	1144 KB	Output is correct

Subtask #9
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	376 KB	Output is correct
2	Correct	6 ms	376 KB	Output is correct
3	Correct	16 ms	380 KB	Output is correct
4	Correct	22 ms	1144 KB	Output is correct

Subtask #10
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	75 ms	404 KB	Output is correct
4	Correct	23 ms	1144 KB	Output is correct

Subtask #11
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	2172 KB	Output is correct
2	Correct	52 ms	2296 KB	Output is correct
3	Correct	70 ms	2940 KB	Output is correct
4	Correct	96 ms	3960 KB	Output is correct
5	Correct	61 ms	3064 KB	Output is correct

Subtask #12
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	4600 KB	Output is correct
2	Correct	339 ms	5624 KB	Output is correct
3	Correct	86 ms	4604 KB	Output is correct
4	Correct	92 ms	3960 KB	Output is correct
5	Correct	98 ms	4764 KB	Output is correct

Subtask #13
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	5216 KB	Output is correct
2	Correct	440 ms	6648 KB	Output is correct
3	Correct	115 ms	5500 KB	Output is correct
4	Correct	125 ms	5912 KB	Output is correct
5	Correct	115 ms	5800 KB	Output is correct

Subtask #14
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	4856 KB	Output is correct
2	Correct	404 ms	6776 KB	Output is correct
3	Correct	122 ms	5624 KB	Output is correct
4	Correct	124 ms	5880 KB	Output is correct
5	Correct	121 ms	5752 KB	Output is correct

Submission #200612

Compilation message