oj.uz

Submission #26626

# Submission time Handle Problem Language Result Execution time Memory
26626 2017-07-03T13:29:54 Z model_code Strongbox (POI11_sej) C++14
100 / 100
 356 ms 3604 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Sejf                                             *
 *   Autor:             Tomasz Kociumaka                                 *
 *   Zlozonosc czasowa: O(sqrt(n)+k*log(n))                              *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *                      proste szukanie dzielnikow, faktoryzacja bez     *
 *                      optymalizacji symuluje mape przez wyszukiwanie   *
 *                      binarne                                          *
 *                                                                       *
 *************************************************************************/
 
#include <cstdio>
#include <vector>
#include <cassert>

#define REP(a,n) for (int a=0; a<(n); ++a)
#define FOR(a,b,c) for (int a=(b); a<=(c); ++a)
#define FORD(a,b,c) for (int a=(b); a>=(c); --a)
#define FORE(i, cnt) for(__typeof((cnt).begin()) i = (cnt).begin(); i != (cnt).end(); ++i)
#define FORED(i, cnt) for(__typeof((cnt).rbegin()) i = (cnt).rbegin(); i != (cnt).rend(); ++i)
#define MP make_pair
#define PB push_back

using namespace std;

typedef long long LL;

template<class T> 
inline int size(const T &t) { return t.size(); }


LL gcd(LL a, LL b) {
    while(b != 0) {
        a %= b;
        swap(a,b);
    }
    return a;
}

vector<LL> dvs; //dzielniki
vector<LL> pDvs; //dzielniki pierwsze
vector<bool> _good; //dobre dzielniki

vector<bool>::iterator good(LL d) {  // emuluje mapę, klucze w dvs, wartości w _good
    int beg = 0, end = size(_good) - 1;
    int med;
    while(end >= beg) {
        med = (beg + end)/2;
        if (dvs[med] == d) return _good.begin()+med;
        else if (dvs[med] < d) beg = med + 1;
        else end = med - 1; 
    }
    assert(false);
}


void computeDivisors(LL n) { //oblicza dvs i pDvs w czasie O(sqrt(n))
    LL m  = n; //do obliczania pDiv
    dvs.PB(1);
    for (int d = 2; d*(LL)d <= n; ++d) { //dzielniki mniejsze niz sqrt(n)
        if (n%d == 0) {
            dvs.PB(d);
            if (m%d == 0) {
                pDvs.PB(d);
                do m/=d; while (m%d == 0);
            }
        }
    }
    //i pozostale
    if (m != 1) pDvs.PB(m);
    int i = size(dvs) - 1;
    if (dvs[i]*dvs[i] == n) --i; //nie wstawiaj sqrt(n) dwa razy
    for (; i >= 0; --i) dvs.PB(n/dvs[i]);
}

int main() {
    LL n;
    int k;
    LL *m;
    scanf("%lld%d", &n, &k);
    m = new LL[k];
    REP(i, k) {
        scanf("%lld", &m[i]);
        m[i] = gcd(m[i], n);
    }
    computeDivisors(n);

    _good = vector<bool>(dvs.size(),true);
    REP(i,k - 1) *good(m[i]) = false;

    LL best = -1; //najlepszy dotychczas znaleziony wynik

    //sprawdzaj od gory dzielniki
    FORED(it, dvs) {
        vector<bool>::iterator git(good(*it));
        if (!*git) continue;
        FORE(jt, pDvs) {
            if ((n / (*it)) % (*jt) != 0) continue; //tak napisane nie spowoduje overflowa
            if (!*good(*it * (*jt))) {
                *git = false;
                break;
            }
        }
        if (*git && m[k-1] % (*it) == 0) {
            best = max(best, n / (*it));
        }
    }
    printf("%lld\n",best);
    delete[] m;
    return 0;
}

Compilation message

sej.cpp: In function 'int main()':
sej.cpp:83:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%d", &n, &k);
                            ^
sej.cpp:86:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &m[i]);
                             ^

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1180 KB Output is correct
2 Correct 19 ms 1324 KB Output is correct
3 Correct 13 ms 1180 KB Output is correct
4 Correct 16 ms 1324 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 1180 KB Output is correct
2 Correct 96 ms 1460 KB Output is correct
3 Correct 129 ms 1180 KB Output is correct
4 Correct 113 ms 1460 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1180 KB Output is correct
2 Correct 126 ms 1460 KB Output is correct
3 Correct 136 ms 1180 KB Output is correct
4 Correct 86 ms 1460 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1180 KB Output is correct
2 Correct 143 ms 1460 KB Output is correct
3 Correct 136 ms 1180 KB Output is correct
4 Correct 106 ms 1460 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 1180 KB Output is correct
2 Correct 173 ms 1656 KB Output is correct
3 Correct 139 ms 1180 KB Output is correct
4 Correct 149 ms 1460 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1180 KB Output is correct
2 Correct 143 ms 1180 KB Output is correct
3 Correct 149 ms 1180 KB Output is correct
4 Correct 139 ms 1460 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 1964 KB Output is correct
2 Correct 219 ms 2432 KB Output is correct
3 Correct 203 ms 2432 KB Output is correct
4 Correct 253 ms 2816 KB Output is correct
5 Correct 206 ms 2436 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 2744 KB Output is correct
2 Correct 293 ms 3212 KB Output is correct
3 Correct 223 ms 2984 KB Output is correct
4 Correct 219 ms 2676 KB Output is correct
5 Correct 283 ms 3184 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 3136 KB Output is correct
2 Correct 313 ms 3604 KB Output is correct
3 Correct 293 ms 3536 KB Output is correct
4 Correct 269 ms 3568 KB Output is correct
5 Correct 283 ms 3600 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 3136 KB Output is correct
2 Correct 316 ms 3604 KB Output is correct
3 Correct 356 ms 3408 KB Output is correct
4 Correct 289 ms 3604 KB Output is correct
5 Correct 289 ms 3596 KB Output is correct