oj.uz

Submission #26628

# Submission time Handle Problem Language Result Execution time Memory
26628 2017-07-03T13:30:40 Z model_code Strongbox (POI11_sej) C++14
70 / 100
 1000 ms 4356 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Sejf                                             *
 *   Autor:             Pawel Parys, Tomasz Kociumaka                    *
 *   Zlozonosc czasowa: O(sqrt(n)+k*log(n)+liczbadzielnikow(n)^2)        *
 *   Opis:              Rozwiazanie powolne                              *
 *                      przerywa po znalezieniu d i swiadka, kolejnosc   *
 *                      rosnace                                          *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <utility>
#include <algorithm>
#include <vector>

#define REP(a,n) for (int a=0; a<(n); ++a)
#define FOR(a,b,c) for (int a=(b); a<=(c); ++a)
#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(); }

const int MAXK = 250000;

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

vector<pair<LL, int> > rozloz(LL N) { // zwraca liste dzielnikow pierwszych+liczba wielokrotnosci
    vector<pair<LL, int> > ret;
    for (int p = 2; p*(LL)p<=N; ++p) {
        int ile = 0;
        while (N%p==0) {
            ++ile;
            N /= p;
        }
        if (ile)
            ret.PB(MP(p, ile));
    }
    if (N>1)
        ret.PB(MP(N, 1));
    return ret;
}

vector<LL> znajdz_dzielniki(LL N) { // zwraca posortowana liste dodatnich dzielnikow liczby N (w tym 1 i N)
    vector<pair<LL, int> > dziel_pier = rozloz(N);
    vector<int> ile(size(dziel_pier)); // ile razy bierzemy ktora liczbe pierwsza
    vector<LL> ret;
    for (LL dz = 1;;) {
        ret.PB(dz);
        for (int a = 0;; ++a)
            if (a>=size(ile)) {
                sort(ret.begin(), ret.end());
                return ret;
            }
            else
            if (ile[a]<dziel_pier[a].second) {
                ++ile[a];
                dz *= dziel_pier[a].first;
                break;
            }
            else
                while (ile[a]) {
                    --ile[a];
                    dz /= dziel_pier[a].first;
                }
    }
}
int K;
LL N, M[MAXK];

int main() {
    scanf("%Ld%d", &N, &K);
    REP(a, K) {
        scanf("%Ld", &M[a]);
        M[a] = gcd(M[a],N);
    }
    sort(M, M+K-1);
    LL* end = unique(M,M+K-1);
    int L = end - M;
    M[L] = M[K-1];
    K = L+1;
    //for (int i = 0; i < K; ++i) printf("%lld\n",M[i]);
    vector<LL> dzielniki = znajdz_dzielniki(N);
    REP(a, size(dzielniki)) {
        LL d = dzielniki[a];
        bool ok = true;
        if (N%d || M[K-1]%d)
            continue;
        REP(a, K-1)
            if (M[a]%d==0) {
                ok = false;
                break;
            }
        if (ok) {
            printf("%lld\n",N/d);
            return 0;
        }
    }
    return 0;
}

Compilation message

sej.cpp: In function 'int main()':
sej.cpp:86:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%Ld%d", &N, &K);
                           ^
sej.cpp:88:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%Ld", &M[a]);
                            ^

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3888 KB Output is correct
2 Correct 0 ms 4028 KB Output is correct
3 Correct 13 ms 3888 KB Output is correct
4 Correct 6 ms 4028 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3888 KB Output is correct
2 Correct 6 ms 4160 KB Output is correct
3 Correct 136 ms 3888 KB Output is correct
4 Correct 16 ms 4160 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3888 KB Output is correct
2 Correct 0 ms 4160 KB Output is correct
3 Correct 129 ms 3888 KB Output is correct
4 Correct 29 ms 4160 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3888 KB Output is correct
2 Correct 3 ms 4160 KB Output is correct
3 Correct 89 ms 3888 KB Output is correct
4 Correct 33 ms 4160 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3888 KB Output is correct
2 Correct 3 ms 4356 KB Output is correct
3 Correct 13 ms 3888 KB Output is correct
4 Correct 13 ms 4160 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3888 KB Output is correct
2 Correct 0 ms 3888 KB Output is correct
3 Correct 119 ms 3888 KB Output is correct
4 Correct 23 ms 4160 KB Output is correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3888 KB Output is correct
2 Correct 53 ms 4356 KB Output is correct
3 Correct 766 ms 4356 KB Output is correct
4 Execution timed out 1000 ms 4356 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 3888 KB Output is correct
2 Correct 153 ms 4356 KB Output is correct
3 Correct 259 ms 4160 KB Output is correct
4 Execution timed out 1000 ms 4160 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 3888 KB Output is correct
2 Correct 243 ms 4356 KB Output is correct
3 Correct 806 ms 4356 KB Output is correct
4 Execution timed out 1000 ms 4356 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3888 KB Output is correct
2 Correct 256 ms 4356 KB Output is correct
3 Execution timed out 1000 ms 4160 KB Execution timed out
4 Halted 0 ms 0 KB -