結果

問題 No.6 使いものにならないハッシュ
ユーザー drymousedrymouse
提出日時 2024-02-14 17:02:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 2,016 bytes
コンパイル時間 952 ms
コンパイル使用メモリ 90,944 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-28 18:56:23
合計ジャッジ時間 2,230 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 19 ms
6,820 KB
testcase_03 AC 4 ms
6,816 KB
testcase_04 AC 5 ms
6,816 KB
testcase_05 AC 6 ms
6,820 KB
testcase_06 AC 12 ms
6,816 KB
testcase_07 AC 7 ms
6,816 KB
testcase_08 AC 10 ms
6,816 KB
testcase_09 AC 5 ms
6,816 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 4 ms
6,816 KB
testcase_12 AC 12 ms
6,820 KB
testcase_13 AC 3 ms
6,816 KB
testcase_14 AC 4 ms
6,816 KB
testcase_15 AC 9 ms
6,820 KB
testcase_16 AC 7 ms
6,816 KB
testcase_17 AC 16 ms
6,816 KB
testcase_18 AC 18 ms
6,816 KB
testcase_19 AC 15 ms
6,816 KB
testcase_20 AC 13 ms
6,816 KB
testcase_21 AC 2 ms
6,820 KB
testcase_22 AC 14 ms
6,820 KB
testcase_23 AC 13 ms
6,820 KB
testcase_24 AC 13 ms
6,820 KB
testcase_25 AC 8 ms
6,820 KB
testcase_26 AC 17 ms
6,820 KB
testcase_27 AC 13 ms
6,816 KB
testcase_28 AC 8 ms
6,820 KB
testcase_29 AC 17 ms
6,816 KB
testcase_30 AC 15 ms
6,816 KB
testcase_31 AC 13 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:88:13: warning: 'maxfirst' may be used uninitialized [-Wmaybe-uninitialized]
   88 |     cout << maxfirst << endl;
      |             ^~~~~~~~
main.cpp:54:9: note: 'maxfirst' was declared here
   54 |     int maxfirst;
      |         ^~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

bool is_prime(int a) {
    if (a < 4) {
        if (a == 1) {return false;}
        else {return true;}
    } else if (a % 2 == 0) {
        return false;
    }
    for (int i = 3; i < sqrt(a) + 2; i+=2) {
        if (a % i == 0) {return false;}
    }
    return true;
}

int sum_digit(int a) {
    int x = a;
    int sum = 0;
    for (int i = 0; i < 6; i++) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int frank_hash(int a) {
    int sum = a;

    for (;sum > 9;) {
        sum = sum_digit(sum);
    }
    return sum;
}

void output(vector<int> a) {
    int l = a.size();
    cout << "[";
    for (int i = 0; i < l; i++) {
        cout << a[i] << ", ";
    }
    cout << "]" << endl;
}

int main(void) {
    int K, N;
    cin >> K >> N;
    //cout << sum_digit(K) << endl;
    //cout << frank_hash(K) << endl;

    int maxfirst;
    int maxlen = 0;
    int curlen = 0;
    vector<int> ps, hs;

    for (int i = K; i < N + 1; i++) {
        if (!is_prime(i)) {continue;}
        int h = frank_hash(i);
        bool is_exest = false;
        for (int j = 0; j < hs.size(); j++) {
            if (hs[j] == h) {
                if (curlen >= maxlen) {
                    maxlen = curlen;
                    maxfirst = ps[0];
                }
                curlen -= j + 1;
                ps.erase(ps.begin(), ps.begin() + j + 1);
                hs.erase(hs.begin(), hs.begin() + j + 1);
                is_exest = true;
                break;
            }
        }
        ps.push_back(i);
        hs.push_back(h);
        curlen++;
        //cout << i << ", " << h << ", " << curlen << ", " << maxlen << ", " << maxfirst << endl;
        //output(ps);
        //output(hs);
    }
    if (curlen >= maxlen) {
        maxlen = curlen;
        maxfirst = ps[0];
    }
    //cout << "max first: " << maxfirst << ", max len: " << maxlen << endl;
    cout << maxfirst << endl;

    return 0;
}
0