#590889 (C++14) No.1312 Snake Eyes

提出ソース

結果

問題	No.1312 Snake Eyes
ユーザー	AngrySadEight
提出日時	2020-12-09 01:10:59
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	106 ms / 2,000 ms
コード長	13,497 bytes
コンパイル時間	1,966 ms
コンパイル使用メモリ	179,552 KB
実行使用メモリ	4,504 KB
最終ジャッジ日時	2023-08-20 11:11:24
合計ジャッジ時間	7,138 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,384 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	1 ms 4,504 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	1 ms 4,380 KB
testcase_13	AC	1 ms 4,380 KB
testcase_14	AC	1 ms 4,380 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	AC	1 ms 4,380 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	1 ms 4,384 KB
testcase_24	AC	1 ms 4,384 KB
testcase_25	AC	2 ms 4,376 KB
testcase_26	AC	1 ms 4,380 KB
testcase_27	AC	1 ms 4,376 KB
testcase_28	AC	2 ms 4,380 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	1 ms 4,380 KB
testcase_31	AC	2 ms 4,376 KB
testcase_32	AC	1 ms 4,380 KB
testcase_33	AC	2 ms 4,376 KB
testcase_34	AC	1 ms 4,376 KB
testcase_35	AC	2 ms 4,376 KB
testcase_36	AC	2 ms 4,380 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	2 ms 4,380 KB
testcase_39	AC	5 ms 4,376 KB
testcase_40	AC	5 ms 4,384 KB
testcase_41	AC	4 ms 4,376 KB
testcase_42	AC	3 ms 4,380 KB
testcase_43	AC	5 ms 4,380 KB
testcase_44	AC	2 ms 4,384 KB
testcase_45	AC	3 ms 4,380 KB
testcase_46	AC	4 ms 4,376 KB
testcase_47	AC	3 ms 4,380 KB
testcase_48	AC	94 ms 4,380 KB
testcase_49	AC	85 ms 4,380 KB
testcase_50	AC	68 ms 4,380 KB
testcase_51	AC	35 ms 4,380 KB
testcase_52	AC	103 ms 4,376 KB
testcase_53	AC	78 ms 4,376 KB
testcase_54	AC	91 ms 4,380 KB
testcase_55	AC	45 ms 4,376 KB
testcase_56	AC	58 ms 4,380 KB
testcase_57	AC	60 ms 4,376 KB
testcase_58	AC	78 ms 4,376 KB
testcase_59	AC	31 ms 4,380 KB
testcase_60	AC	57 ms 4,380 KB
testcase_61	AC	103 ms 4,380 KB
testcase_62	AC	40 ms 4,376 KB
testcase_63	AC	2 ms 4,376 KB
testcase_64	AC	5 ms 4,380 KB
testcase_65	AC	13 ms 4,380 KB
testcase_66	AC	2 ms 4,380 KB
testcase_67	AC	2 ms 4,376 KB
testcase_68	AC	6 ms 4,380 KB
testcase_69	AC	2 ms 4,380 KB
testcase_70	AC	85 ms 4,380 KB
testcase_71	AC	51 ms 4,380 KB
testcase_72	AC	6 ms 4,376 KB
testcase_73	AC	2 ms 4,380 KB
testcase_74	AC	2 ms 4,376 KB
testcase_75	AC	2 ms 4,376 KB
testcase_76	AC	102 ms 4,376 KB
testcase_77	AC	106 ms 4,376 KB
testcase_78	AC	104 ms 4,380 KB
testcase_79	AC	77 ms 4,380 KB
testcase_80	AC	105 ms 4,380 KB
testcase_81	AC	103 ms 4,376 KB
testcase_82	AC	103 ms 4,376 KB
testcase_83	AC	103 ms 4,376 KB
testcase_84	AC	104 ms 4,376 KB
testcase_85	AC	96 ms 4,384 KB
testcase_86	AC	90 ms 4,376 KB
testcase_87	AC	51 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

vector<ll> bitconversion(ll i, ll n, ll N){
    //数字iをn進数にして，長さNの配列にして返す。
    //例えば，bitconversion(33,3,4)={1,0,2,0}。
    ll x = 1;
    rep(j,N){
        x *= n;
    }
    vector<ll> vec(N);
    rep(j,N){
        x /= n;
        vec[j] = i / x;
        i -= x * vec[j];
    }
    return vec;
}

int ctoi(char c){
    //char型の1桁の数をint型に変える。
    switch (c){
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default: return 0;
    }
}


vector<int> topological_sort(vector<vector<int> > &connection, vector<int> &count, int N){
    //vectorをトポロジカルソートして返す。
    //connectionにはそこからたどり着くことの出来る頂点の番号をあらかじめ入れておく。
    //countにはその頂点に入ってくる頂点の数を入れておく。
    vector<int> ans(0);
    queue<int> que;
    
    for (int i = 0; i < N; i++){
        if (count[i] == 0){
            que.push(i);
        }
    }
    
    while(que.size() != 0){
        int v = que.front();
        que.pop();
        
        for (int i = 0; i < connection[v].size(); i++){
            count[connection[v][i]] -= 1;
            if (count[connection[v][i]] == 0){
                que.push(connection[v][i]);
            }
        }
        ans.push_back(v);
    }
    
    return ans;
}

struct union_find{
    vector<int> par;
    vector<int> rank;
    vector<int> siz;
    
    union_find(int N) : par(N), rank(N), siz(N){
        rep(i,N){
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    //宣言パート。union_findを宣言する時は，例えばunion_find tree(N)のようにする。
    
    int root(int x){
        if (par[x] == x){
            return x;
        }
        return par[x] = root(par[x]);
    }
    //頂点に対して，その根となる頂点の番号を返す。
    
    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]){
            par[rx] = ry;
            siz[ry] += siz[rx];
        }
        else{
            par[ry] = rx;
            siz[rx] += siz[ry];
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
    }
    //頂点xとyをくっつけてやる。計算量削減のため，それぞれの木の「高さ」(rank)をカウントしておいて，
    //その高さの高い方に低い方をくっつけてやるようにする。
    
    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    //頂点xとyが同じ木に属するかを判定する。
    
    int size(int x){
        return siz[root(x)];
    }
    //頂点xが含まれる木のサイズ。
};

int gcd(int a, int b){
    //aとbの最大公約数。
    int r,temp;
    if (a < b){
        temp = a;
        a = b;
        b = temp;
    }
    while ( (r = a % b) != 0){
        a = b;
        b = r;
    }
    return b;
}

ll iterative_square_method(ll i, vector<ll> &vec, ll N, ll mod){
    //繰り返し二乗法。iのX乗をmodで割った余りを求める。
    //なお，Xは，事前にmoddividing関数で長さNの二進数vector(vec)に直しておく必要がある。
    //例えば，2の100000乗をmod1e9+7で求めたいときは，
    //iterative_square_method(2,moddividing(100000,2,30),30,1000000007)のように書けば良い。
    ll ans = 1;
    rep(j,N){
        if (vec[N - 1 - j] == 1) ans = (ans * i) % mod;
        i = (i * i) % mod;
    }
    return ans;
}

ll moddividing(ll x,ll y){
    //x÷yをmod1e9+7で求める。
    vector<ll> vec(30);
    rep(i,30){
        vec[i] = y;
        y = y * y % 1000000007;
    }
    ll c = x;
    c = c * vec[0] % 1000000007;
    c = c * vec[2] % 1000000007;
    c = c * vec[9] % 1000000007;
    c = c * vec[11] % 1000000007;
    c = c * vec[14] % 1000000007;
    c = c * vec[15] % 1000000007;
    c = c * vec[17] % 1000000007;
    c = c * vec[19] % 1000000007;
    c = c * vec[20] % 1000000007;
    c = c * vec[23] % 1000000007;
    c = c * vec[24] % 1000000007;
    c = c * vec[25] % 1000000007;
    c = c * vec[27] % 1000000007;
    c = c * vec[28] % 1000000007;
    c = c * vec[29] % 1000000007;
    return c;
}

ll moddividing2(ll x,ll y){
    //x÷yをmod998244353で求める。
    vector<ll> vec(30);
    rep(i,30){
        vec[i] = y;
        y = y * y % 998244353;
    }
    ll c = x;
    c = c * vec[0] % 998244353;
    c = c * vec[1] % 998244353;
    c = c * vec[2] % 998244353;
    c = c * vec[3] % 998244353;
    c = c * vec[4] % 998244353;
    c = c * vec[5] % 998244353;
    c = c * vec[6] % 998244353;
    c = c * vec[7] % 998244353;
    c = c * vec[8] % 998244353;
    c = c * vec[9] % 998244353;
    c = c * vec[10] % 998244353;
    c = c * vec[11] % 998244353;
    c = c * vec[12] % 998244353;
    c = c * vec[13] % 998244353;
    c = c * vec[14] % 998244353;
    c = c * vec[15] % 998244353;
    c = c * vec[16] % 998244353;
    c = c * vec[17] % 998244353;
    c = c * vec[18] % 998244353;
    c = c * vec[19] % 998244353;
    c = c * vec[20] % 998244353;
    c = c * vec[21] % 998244353;
    c = c * vec[22] % 998244353;
    c = c * vec[24] % 998244353;
    c = c * vec[25] % 998244353;
    c = c * vec[27] % 998244353;
    c = c * vec[28] % 998244353;
    c = c * vec[29] % 998244353;
    return c;
}

struct segtree{
    //セグメントツリー。いろんな機能があるよ。やったね。
    vector<int> vec;
    
    segtree(int N) : vec(N){
        rep(i,N){
            vec[i] = 0;
        }
    }
    //初期化。セグメントツリーの正体はvectorである。
    //バグが発生する可能性があるため，サイズNは（用意したいセグ木の長さ）*2よりも大きい2の累乗数で宣言してやる。
    
    void make(int k, int a, int N){ //0_indexed
        k += (N / 2);
        vec[k] = a;
    }
    //セグメントツリーのk番目の要素をaに変える。
    
    void sum_update(int k, int a, int N){ //0_indexed
        k += (N / 2);
        vec[k] = a;
        while(k > 1){
            k = k / 2;
            vec[k] = vec[k * 2] + vec[k * 2 + 1];
        }
    }
    //セグメントツリー上で和の計算を行う上での前処理。k番目の要素をaに変更して，なおかつ和の計算の前処理を行う。
    
    void max_update(int k, int a, int N){ //0_indexed
        k += (N / 2);
        vec[k] = a;
        while(k > 1){
            k = k / 2;
            vec[k] = max(vec[k * 2], vec[k * 2 + 1]);
        }
    }
    //セグメントツリー上で最大値を求める上での前処理。k番目の要素をaに変更して，なおかつ最大値を求める前処理を行う。
    
    void min_update(int k, int a, int N){ //0_indexed
        k += (N / 2);
        vec[k] = a;
        while(k > 1){
            k = k / 2;
            vec[k] = min(vec[k * 2], vec[k * 2 + 1]);
        }
    }
    //セグメントツリー上で最小値を求める上での前処理。k番目の要素をaに変更して，なおかつ最小値を求める前処理を行う。
    
    int min_query(int a, int b, int k, int l, int r){ // min_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
        if (r <= a || b <= l) return 1000000000;
        if (a <= l && r <= b) return vec[k];
        int vl = min_query(a, b, k * 2, l, (l + r) / 2);
        int vr = min_query(a, b, k * 2 + 1, (l + r) / 2, r);
        return min(vl,vr);
    }
    //セグメントツリー上で最小値を求める。半開区間[a,b)(a,bは0_indexed)における最小値を求めてやる。
    //k,l,rは固定で，k=1,l=0,r=N/2として良い。
    
    int check(int i){
        return vec[i];
    }
    //i番目の要素を確認する。
    
    int max_query(int a, int b, int k, int l, int r){ // max_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
        if (r <= a || b <= l) return -1000000000;
        if (a <= l && r <= b) return vec[k];
        int vl = max_query(a, b, k * 2, l, (l + r) / 2);
        int vr = max_query(a, b, k * 2 + 1, (l + r) / 2, r);
        return max(vl,vr);
    }
    //セグメントツリー上で最大値を求める。半開区間[a,b)(a,bは0_indexed)における最大値を求めてやる。
    //k,l,rは固定で，k=1,l=0,r=N/2として良い。
    
    int sum_query(int a, int b, int k, int l, int r){ // sum_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return vec[k];
        int vl = sum_query(a, b, k * 2, l, (l + r) / 2);
        int vr = sum_query(a, b, k * 2 + 1, (l + r) / 2, r);
        return vl + vr;
    }
    //セグメントツリー上で和を求める。半開区間[a,b)(a,bは0_indexed)における和を求めてやる。
    //k,l,rは固定で，k=1,l=0,r=N/2として良い。
    
};

char itoc(int c){
    //int型の0から25までの値cを，(c+1)番目のchar型アルファベット1文字に変更してやる。
    switch (c){
        case 0: return 'a';
        case 1: return 'b';
        case 2: return 'c';
        case 3: return 'd';
        case 4: return 'e';
        case 5: return 'f';
        case 6: return 'g';
        case 7: return 'h';
        case 8: return 'i';
        case 9: return 'j';
        case 10: return 'k';
        case 11: return 'l';
        case 12: return 'm';
        case 13: return 'n';
        case 14: return 'o';
        case 15: return 'p';
        case 16: return 'q';
        case 17: return 'r';
        case 18: return 's';
        case 19: return 't';
        case 20: return 'u';
        case 21: return 'v';
        case 22: return 'w';
        case 23: return 'x';
        case 24: return 'y';
        case 25: return 'z';
        default: return 'a';
    }
}

int vector_finder(vector<int> &vec, int number){
    //int型のvectorの中にその要素が含まれているかを，計算量O(len(vec))で求める。
    //含まれていれば1を，含まれていなければ0を返す。
    int len = vec.size();
    int cnt = 0;
    rep(i,len){
        if (vec[i] == number) cnt++;
    }
    if (cnt >= 1) return 1;
    else return 0;
}

int vector_finder_rapid(vector<int> &vec, int number){
    //vector_finderの高速版。先ほどが線型探索だったのに対し，こちらは二分探索にしてある。計算量はO(log(len(vec)))
    //ただし，二分探索する以上，vectorは事前にソートしてから渡す必要がある。
    int len = vec.size();
    int cnt = -1;
    int left = 0;
    int right = len - 1;
    if (vec[left] > number) cnt += 1;
    else if (vec[right] < number) cnt += 1;
    else if (vec[left] == number) cnt += 2;
    else if (vec[right] == number) cnt += 2;
    else{
        while(true){
            if (right - left == 1){
                if (vec[left] == number) cnt += 2;
                else cnt += 1;
                break;
            }
            else{
                if (vec[(left + right) / 2] <= number){
                    left = (left + right) / 2;
                }
                else{
                    right = (left + right) / 2;
                }
            }
        }
    }
    return cnt;
}

void vector_print(vector<ll> &vec){
    //一次元vectorの要素を全て空白区切りで出力して，最後に改行する。
    int len = vec.size();
    rep(i,len - 1){
        cout << vec[i] << " ";
    }
    cout << vec[len - 1] << endl;
}

void vector_print2(vector<int> &vec){
    //一次元vectorの要素を全て改行して出力する。
    int len = vec.size();
    rep(i,len){
        cout << vec[i] << endl;
    }
}

void vector_print3(vector<vector<int> > &vec){
    //二次元vectorの要素を全て空白区切りで出力して，最後に改行する。
    int len1 = vec.size();
    rep(i,len1){
        int len2 = vec[i].size();
        rep(j,len2 - 1){
            cout << vec[i][j] << " ";
        }
        cout << vec[i][len2 - 1] << endl;
    }
}

int main(){
    ll N;
    cin >> N;
    vector<pair<ll,ll> > isdivisor(0);
    for (ll i = 1; i * i < N; i++){
        if (N % i == 0){
            isdivisor.push_back(pair<ll,ll> (i, N / i));
        }
    }
    ll min_ans = N;
    for (ll i = 2; i * i < N; i++){
        ll times = 1;
        ll num = 1;
        while(true){
            if (num * i > N){
                break;
            }
            else{
                num *= i;
                times++;
            }
        }
        vector<ll> bin = bitconversion(N,i,times);
        bool same = true;
        ll first_num = bin[0];
        for (ll j = 0; j < times; j++){
            if (first_num != bin[j]) same = false;
        }
        if (same) min_ans = min(min_ans,i);
    }
    for (ll i = 0; i < isdivisor.size(); i++){
        if (isdivisor[i].second - isdivisor[i].first >= 2) min_ans = min(min_ans, isdivisor[i].second - 1);
    }
    if (N == 1) cout << 2 << endl;
    else if (N == 2) cout << 3 << endl;
    else cout << min_ans << endl;
}

yukicoder

結果

テストケース

ソースコード