# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44114 | 2018-03-30T00:08:16 Z | imaxblue | Strongbox (POI11_sej) | C++17 | 1000 ms | 14560 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define pq priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() ((rand() << 14)+rand()) #define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0) char _; #define pi 3.14159265358979323846 ll gcd(ll x, ll y){return y==0?x:gcd(y, x%y);} vector<ll> f; ll d; ll n, a[250005], k, g; set<ll> s; void factor(ll X){ for (ll l=1; l*l<=X; ++l){ if (X%l==0){ f.pb(l); if (l*l!=X) f.pb(X/l); } } sort(f.begin(), f.end()); } bool check(ll G){ if (g/G<n*20){ for(ll l=G; l<g; l+=G) if (s.count(l)) return 0; return 1; } fox(l, n){ if ((a[l]%g)%G==0) return 0; } return 1; } int main(){ scanf("%lli%lli", &d, &n); --n; fox(l, n) scan(a[l]); scanf("%lli", &k); g=gcd(k, d); fox(l, n){ a[l]%=g; s.insert(a[l]); } //return 0; //cout << k << ' ' << d << ' ' << g << endl; factor(g); fox(l, f.size()){ //cout << f[l] << endl; if (check(f[l])){ cout << d/f[l]; return 0; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 428 KB | Output is correct |
2 | Correct | 2 ms | 488 KB | Output is correct |
3 | Correct | 2 ms | 620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 620 KB | Output is correct |
2 | Correct | 2 ms | 620 KB | Output is correct |
3 | Correct | 2 ms | 620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 620 KB | Output is correct |
2 | Correct | 2 ms | 620 KB | Output is correct |
3 | Correct | 4 ms | 620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 620 KB | Output is correct |
2 | Correct | 2 ms | 620 KB | Output is correct |
3 | Correct | 15 ms | 620 KB | Output is correct |
4 | Correct | 17 ms | 716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 716 KB | Output is correct |
2 | Correct | 4 ms | 716 KB | Output is correct |
3 | Correct | 2 ms | 716 KB | Output is correct |
4 | Correct | 105 ms | 876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 876 KB | Output is correct |
2 | Correct | 3 ms | 876 KB | Output is correct |
3 | Correct | 131 ms | 876 KB | Output is correct |
4 | Correct | 88 ms | 876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 97 ms | 876 KB | Output is correct |
2 | Correct | 3 ms | 876 KB | Output is correct |
3 | Correct | 2 ms | 876 KB | Output is correct |
4 | Correct | 119 ms | 892 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 892 KB | Output is correct |
2 | Correct | 3 ms | 892 KB | Output is correct |
3 | Correct | 2 ms | 892 KB | Output is correct |
4 | Correct | 128 ms | 976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 976 KB | Output is correct |
2 | Correct | 6 ms | 976 KB | Output is correct |
3 | Correct | 90 ms | 976 KB | Output is correct |
4 | Correct | 132 ms | 976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 175 ms | 6104 KB | Output is correct |
2 | Correct | 165 ms | 6104 KB | Output is correct |
3 | Execution timed out | 1082 ms | 6228 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 185 ms | 10672 KB | Output is correct |
2 | Correct | 134 ms | 10672 KB | Output is correct |
3 | Execution timed out | 1083 ms | 11500 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 233 ms | 14296 KB | Output is correct |
2 | Correct | 199 ms | 14296 KB | Output is correct |
3 | Execution timed out | 1057 ms | 14296 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 258 ms | 14304 KB | Output is correct |
2 | Correct | 198 ms | 14304 KB | Output is correct |
3 | Execution timed out | 1083 ms | 14560 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |