oj.uz

Submission #1013368

# Submission time Handle Problem Language Result Execution time Memory
1013368 2024-07-03T12:58:33 Z vjudge1 Strongbox (POI11_sej) C++17
70 / 100
 1000 ms 2520 KB 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
namespace debug { template <class c> struct rge { c b, e; }; template <class c> rge<c> range(c i, c j) { return rge<c>{i, j}; } template <class c> char spk(...); template <class c> auto spk(c* a) -> decltype(cerr << *a, 0); struct stream { ~stream() { cerr << endl; } template <class c> typename enable_if <sizeof spk<c>(0) != 1, stream&>::type operator<<(c i) { cerr << boolalpha << i; return *this; } template <class c> typename enable_if <sizeof spk<c>(0) == 1, stream&>::type operator<<(c i) { return *this << range(begin(i), end(i)); } template <class a, class b> stream& operator<<(pair <a,b> p) { return *this << "(" << p.first << ", " << p.second << ")"; } template <class c> stream& operator<<(rge<c> d) { *this << "["; for (auto it=d.b; it!=d.e; it++) *this << ", " + 2 * (it == d.b) << *it; return *this << "]"; } stream& _dbg(const string& s, int i, int b) { return *this; } template <class c, class ... cs> stream& _dbg(const string& s, int i, int b, c arg, cs ... args) { if (i == (int)(s.size())) return (*this << ": " << arg); b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{') - (s[i] == ')') - (s[i] == ']') - (s[i] == '}'); return (s[i] == ',' && b == 0) ? (*this << ": " << arg << "     ")._dbg(s, i + 1, b, args...) : (s[i] == ' ' ? *this : *this << s[i])._dbg(s, i + 1, b, arg, args...); } };}
#define dout debug::stream()
#define dbg(...) ((dout << ">> ")._dbg(#__VA_ARGS__, 0, 0, __VA_ARGS__))
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define ss(x) ((int)((x).size()))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(b);i>=(a);i--)
#define upgrade cin.tie(0)->sync_with_stdio(0);
template <class p, class q> pair<p,q> operator-(pair<p,q> a, pair<p,q> b) { return mp(a.f - b.f, a.s - b.s); }
template <class p, class q> pair<p,q> operator+(pair<p,q> a, pair<p,q> b) { return mp(a.f + b.f, a.s + b.s); }
template <class p, class q> void umin(p &a, const q &b) { if (a > b) a = b; }
template <class p, class q> void umax(p &a, const q &b) { if (a < b) a = b; }
using lf = long double;
using ll = long long;
using cll = const ll;
using cint = const int;

bool check(ll d, vector <ll>& vec)
{
	for (ll m : vec){
		if (m % d == 0){
			return false;
		}
	}
	return true;
}

int main()
{
	ll N;
	int k;
	
	scanf("%lld%d", &N, &k);

	vector <ll> m(k);

	for (ll& x : m) scanf("%lld", &x);

	ll n = __gcd(N, m.back());
	m.pop_back();
	
	for (ll& x : m) x = __gcd(x, n);

	//sort(all(m));

	//m.erase(unique(all(m)), m.end());
	
	//reverse(all(m));

	vector <ll> divs;

	for (ll i = 1; i * i <= n; i++){
		if (n % i != 0) continue;
		divs.pb(i);
		if (i * i < n) divs.pb(n / i);
	}

	sort(all(divs));

//	dbg(n, divs);

	for (ll d : divs){
		if (check(d, m) == true){
			printf("%lld\n", N / d);
			return 0;
		}
	}

	assert(false);
}

Compilation message

sej.cpp: In function 'int main()':
sej.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%lld%d", &N, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
sej.cpp:47:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  for (ll& x : m) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 348 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 19 ms 700 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 23 ms 440 KB Output is correct
4 Correct 15 ms 648 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 19 ms 604 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 23 ms 644 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 16 ms 344 KB Output is correct
4 Correct 24 ms 688 KB Output is correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1228 KB Output is correct
2 Correct 21 ms 1112 KB Output is correct
3 Correct 805 ms 1616 KB Output is correct
4 Execution timed out 1072 ms 1876 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1884 KB Output is correct
2 Correct 27 ms 1884 KB Output is correct
3 Correct 927 ms 2176 KB Output is correct
4 Execution timed out 1090 ms 1872 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2396 KB Output is correct
2 Correct 36 ms 2400 KB Output is correct
3 Execution timed out 1069 ms 2520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2392 KB Output is correct
2 Correct 34 ms 2400 KB Output is correct
3 Execution timed out 1058 ms 2396 KB Time limit exceeded
4 Halted 0 ms 0 KB -