結果

問題 No.1729 ～サンプルはちゃんと見て！～　16進数と8進数(1)
ユーザー Kyo_s_sKyo_s_s
提出日時 2021-11-05 21:43:10
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 13,727 bytes
コンパイル時間 4,254 ms
コンパイル使用メモリ 251,444 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-24 05:29:27
合計ジャッジ時間 4,579 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region header
#include <bits/stdc++.h>
using namespace std;
/* alias */
using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vf = vector<float>;
using vd = vector<double>;
using vdd = vector<vd>;
using vvf = vector<vf>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vvs = vector<vs>;
using vc = vector<char>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using qll = queue<ll>;
typedef complex<double> cd;
//仮想配列map<> https://code-database.com/knowledges/100
//優先度付きque https://atcoder.jp/contests/apg4b/tasks/APG4b_aa

/* define short */
#define MOD 1000000007
#define INF LLONG_MAX/32
#define elif else if
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mp make_pair
#define all(obj) (obj).begin(), (obj).end()
#define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/* REP macro */
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) reps(i, 1, n + 1)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define rrepd(i,n) for(ll i=n;i>=1;i--)


//小数点以下出力の時にmainに書く
// cout << fixed << setprecision(10);

#define debug(x) cerr << #x << ":" << x << endl;

#pragma endregion header    

ll N;


vvll Graph;/*グラフ*/
ll H, W; vs HW;/*HW .#*/

struct edge{ll to, cost;};
vector<vector<edge>> G;


#pragma region fanction
#pragma region First Search
/*幅優先探索 vll dist(N,-1); Graphは隣接リスト*/
void bfs(vll &dist, ll fq, vvll Graph){
    dist[fq] = 0;
    deque<ll> que;que.pb(fq);
    ll v;
    while(!que.empty()){
        v = que.front();que.pop_front();

        for(ll nv:Graph[v]){
            if(dist[nv] != -1) continue;
            dist[nv] = dist[v] + 1;
            que.pb(nv);
        }
    }
}


/*distにsysxからの距離が入る　各重み1*/
/*HW幅優先探索 https://pyteyon.hatenablog.com/entry/2019/03/01/211133#%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2*/
/*vvll dist(H vll(W)); rep(h,H) rep(w,W) dist[h][w] = INF;*/
void HW_bfs(vvll &dist, ll sy, ll sx, vs HW){
    dist[sy][sx] = 0;
    deque<vll> que;
    que.pb({sy,sx});

    vll v;
    ll nowy, nowx, nexty,nextx;
    vvll dydx = {{1,0},{0,1},{-1,0},{0,-1}};

    //重み1ならpbしてd++ 重み0ならpfしてそのままdiseにd入れれば01bfs
    //que.back();que.pop_back()で深さ優先探索

    while(!que.empty()){
        v = que.front();que.pop_front();
        nowy = v[0]; nowx = v[1];
        for(vll dyx:dydx){
            nexty = nowy+dyx[0]; nextx = nowx+dyx[1];
            if(!(0 <= nexty && nexty < H && 0 <= nextx && nextx < W)) continue;
            if(HW[nexty][nextx] == 'o' && dist[nexty][nextx] == INF){
                que.pb({nexty,nextx});
                dist[nexty][nextx] = dist[nowy][nowx] + 1;
            }
        }
    }
}

/*深さ優先探索 vll dist(N,-1); Graphは隣接リスト スタートのdistを0にすること！*/
void dfs(vll &dist, ll v, vvll &Graph){
    for(ll nv:Graph[v]){
        if(dist[nv] != -1) continue;
        dist[nv] = dist[v] + 1;
        dfs(dist,nv,Graph);
    }
}

//単一始点最短経路　ダイクストラ　O(MlogN)
//vector<vector<pll>> G //G; fi:to se:cost
// Graph.resize(N);
// rep(i,M){
//     ll a,b,c; cin >> a >> b >> c;
//     a--;b--;
//     Graph[a].pb(pll(b,c));
//     Graph[b].pb(pll(a,c));
// }

//Gで呼べばOK
vll dijkstra(ll start,vector<vector<edge>> &G){
    vll dist(N,INF);
    priority_queue<pll,vector<pll>,greater<pll>> que;
    dist[start] = 0;
    que.push(pll(dist[start],start));
    while (!que.empty()){
        pll p = que.top(); que.pop();
        ll v = p.second;
        if(dist[v] < p.first) continue;
        for(auto &e:G[v]){
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                que.push(pll(dist[e.to],e.to));
            }
        }
    }

    return dist;
}

/*analyze*/
struct Gr{ bool ki; ll sz; ll parent;};

void analyzedfs(vb &vis, ll now, ll bef, Gr &add,bool &t, vvll &Graph){
    add.sz++;
    for(auto nxt:Graph[now]) if(nxt != bef){
        if(nxt == now) t = true;
        if(vis[nxt]){
            add.ki = false;
        }else{
            vis[nxt] = true;
            analyzedfs(vis,nxt,now,add,t,Graph);
        }
    }
}

// /*Graphの中の複数のグラフを分解、サイズと親の番号を返す*/
vector<Gr> analyze(vvll &Graph){
    /*Grはbool ki, ll sz,parentからなる　kiは木かどうかをtrue,falseで返す*/
    /*szはサイズ　parentはそのグラフの中で一番小さい頂点*/
    vector<Gr> ret;
    vb vis(Graph.size(),false);
    rep(i,Graph.size()){
        if(vis[i]) continue;
        vis[i] = true;
        Gr add = {true,0,i};
        bool t = false;//自己ループ単体は0,1として返す
        analyzedfs(vis,i,-1,add,t,Graph);
        if(add.sz > 1) ret.pb(add);
        elif(t) ret.pb({0,1});
    }
    return ret;
}


#pragma endregion First Search
#pragma region MOD
const ll nCkMax = 1e6;
vll fac(1,0),finv(1,0),inv(1,0);

void COMinit(){
    fac.resize(nCkMax);
    finv.resize(nCkMax);
    inv.resize(nCkMax);
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(ll i=2;i<nCkMax;i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
/*a^n % mod p O(log N)*/
ll modpow(ll a, ll n) {
    if(n == 0) return 1;
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
/*a! mod p O(N)*/
ll modfac(ll n){
    ll ret = 1;
    rrep(i,n){
        ret *= i;
        ret %= MOD;
    }
    return ret;
}

/*nCk % mod 前処理O(N) クエリ処理O(1)*/
ll nCk(ll n, ll k){
    if(fac[0] != 1) COMinit();//初期化 O(N)
    if(n<k) return 0;
    if(n<0 || k<0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll nHk(ll n, ll k){
    return nCk(n+k-1,k);
}

ll factorial(ll n){
    ll ans = 1;
    for (ll i = 1;i<=n;i++){
        ans = ans * i % MOD;
    }
    return ans;
}
#pragma endregion MOD
#pragma region array

/*一次元配列最大最小総和*/
ll vmax(vll array){
    ll Max = -INF;
    for(ll a:array) chmax(Max,a);
    return Max;
}

ll vmin(vll array){
    ll Min = INF;
    for(ll a:array) chmin(Min,a);
    return Min;
}

ll sum(vll &array){
    ll Sum = 0;
    for(ll a:array) Sum += a;
    return Sum;
}

/*累積和 先頭に0が追加されてる lからrまではret[r+1]-ret[l]*/
vll cumulatice_sum(vll &array){
    vll ret(array.size()+1,0);
    rep(i,array.size()) ret[i+1] = ret[i] + array[i];
    return ret;
}

/*累積和 先頭に0が追加されてる lからrまでは(ret[r+1]-ret[l]+MOD)%MOD*/
vll cumulatice_sum_mod(vll &array){
    vll ret(array.size()+1,0);
    rep(i,array.size()) ret[i+1] = (ret[i] + array[i]) % MOD;
    return ret;
}

/*重複消し*/
void list_set(vll &array){
    sort(all(array));
    array.erase(unique(all(array)),array.end());
}

/*vvllで格納されてる配列をkey番目の要素でソート*/
void vvllsort(vvll &array, ll key){
    sort(all(array),[&key](vll a,vll b){return a[key] < b[key];});
}

/*座標圧縮*/
ll comp(vector<ll> &A){
    std::map<ll,ll> mem;
    for(auto p: A) mem[p] = 0;
    ll sz = 0;
    for(auto &p: mem) p.second = sz++;
    for(auto &p: A) p = mem[p];
    return sz;
}

/*string Sに何個string Kが含まれるか 一文字でもいいけどcharじゃなくてstringにしてね*/
ll stringinstring(string &S,string K){
    ll ret = 0;
    rep(i,S.size()-K.size()+1){
        bool f = true;
        rep(j,K.size()) if(S[i+j] != K[j]) f=false;
        if(f) ret++;
    }
    return ret;
}
#pragma endregion array
#pragma region frac
struct frac{
    ll c, m;    //child, mother c/m

    void simplify(){
        ll g = gcd(c, m);
        c /= g; m /= g;
        return;
    }

    frac operator+(frac &x){
        frac res(*this);
        res = {res.c * x.m + x.c * res.m, res.m * x.m};
        return res;
    }

    frac operator-(frac &x){
        frac res(*this);
        res = {res.c * x.m - x.c * res.m, res.m * x.m};
        return res;
    }

    frac operator/(frac &x){
        frac res(*this);
        res = {res.c * x.m, res.m * x.c};
        return res;
    }

    frac operator*(frac &x){
        frac res(*this);
        res = {res.c * x.c, res.m * x.m};
        return res;
    }

    bool operator==(frac &x){ return (c * x.m == m * x.c);}
    bool operator>(frac &x){ return (c * x.m > m * x.c);}
    bool operator>=(frac &x){ return (c * x.m >= m * x.c);}
    bool operator<(frac &x){ return (c * x.m < m * x.c);}
    bool operator<=(frac &x){ return (c * x.m <= m * x.c);}
};

#pragma endregion UnionFind
#pragma region bisect
/*二分探索*/
ll bisect_left(vll &array, ll key){
    return lower_bound(all(array),key) - array.begin();
}

ll bisect_right(vll &array, ll key){
    return upper_bound(all(array),key) - array.begin();
}

/*最長増加部分列  dpがright:i<jでai <= aj left:i<jでai < aj*/
ll LIS(vll a){
    vll dp(a.size(),INF);
    rep(i,a.size()){
        dp[bisect_right(dp,a[i])] = a[i];
    }
    return bisect_left(dp,INF);
}


/*条件を満たす最大のokを返す　最小にしたいならokng逆にする solveを書き換えること!　ok:解が存在する値 ng:解が存在しない値*/
bool solve(ll n){
    bool ret = true;
    return ret;
}

ll meguru_bisect(ll ok, ll ng){
    ll mid;
    while(abs(ok-ng) > 1){
        mid = (ok + ng) / 2;
        if(solve(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
#pragma endregion bisect
#pragma region others

/* memo
二次元配列の90度回転
// i:j 
// j:N - i - 1
*/

/*普通のa^n*/
ll mpow(ll a, ll n){
    if(n==0) return 1;
    ll res = 1;
    while (n > 0) {
        if (n & 1) res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}
/*最大公約数*/
ll gcd(ll x,ll y){
    if (x < y) swap(x,y);
    while (y > 0){
        ll r = x % y;
        x = y;
        y = r;
    }
    return x;
}
/*最小公倍数*/
ll lcm(ll x,ll y){
    return x * y / (gcd(x,y));
}
/*約数列挙*/
vll divisor(ll n){
    vll ret;
    for (ll i = 1; i * i <= n; i++){
        if (n % i == 0){
            ret.pb(i);
            if (i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}
/*素因数分解*/
vll factorize(ll n){
    vll ret;
    while (n % 2 == 0){
        ret.pb(2);
        n /= 2;
    }
    ll f = 3;
    while (f * f <= n){
        if (n % f == 0){
            ret.pb(f);
            n /= f;
        }else f += 2;
    }
    if (n != 1) ret.pb(n);
    return ret;
}
const ll Eramax = 1e6+1;
vll Eratos(1,1);
void Erainit(){
    Eratos.resize(Eramax+1);
    rep(i,Eramax+1) Eratos[i] = i;
    for(ll i=2;i<Eramax;i++){
        if(Eratos[i] != i) continue;
        for(ll j=2*i;j<Eramax;j+=i) Eratos[j] = i;
    }
    Eratos[1] = -1;
}
//前処理型素因数分解　1e6以下を複数回やるならこっち
vll Era_factorize(ll n){
    if(Eratos[0] != 0) Erainit();
    vll ret = {};
    if(n==1) return ret;
    while(n!=1){
        ret.pb(Eratos[n]);
        n /= Eratos[n];
    }
    return ret;
}

double distanc(cd p0, cd c1, cd c2){
    // c1原点に移動
    p0 -= c1;
    c2 -= c1;
    // 回転
    auto u = c2 / abs(c2);
    p0 /= u;
    return p0.imag();
}

/* x,y から sx,sy ->gx,gyの垂線の距離を算出 */
double distance(ll x, ll y, ll sx, ll sy, ll gx, ll gy){
    // distancで複素数で計算してる　垂線の距離なのでsxsy-gxgyが短いときはうまく距離が出せない
    return distanc(cd(x,y),cd(sx,sy),cd(gx,gy));
}

/*3点が同一線上にあるか？　*/
bool isonLine(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){
    ll dx1 = x1 - x2;
    ll dy1 = y1 - y2;
    ll dx2 = x1 - x3;
    ll dy2 = y1 - y3;
    return dx2 * dy1 == dx1 * dy2;
}

#pragma endregion others
#pragma endregion fanction



int main(){
    map<char,string> A;
    A['0'] = "0000";
    A['1'] = "0001";
    A['2'] = "0010";
    A['3'] = "0011";
    A['4'] = "0100";
    A['5'] = "0101";
    A['6'] = "0110";
    A['7'] = "0111";
    A['8'] = "1000";
    A['9'] = "1001";
    A['A'] = "1010";
    A['B'] = "1011";
    A['C'] = "1100";
    A['D'] = "1101";
    A['E'] = "1110";
    A['F'] = "1111";
    

    string S; cin >> S;
    string N;//S.length() * 4 tu
    if(S.length() * 4 % 3 == 1) N += "00";
    elif(S.length() * 4 % 3 == 2) N += '0';
    for(auto s:S){
        N += A[s];
    }

    vll cnt(8,0);

    while(!N.empty()){
        string t;
        rep(i,3){
            t += N.back(); N.pop_back();
        }
        reverse(all(t));

        if(t == "000") cnt[0]++;
        elif(t == "001") cnt[1]++;
        elif(t == "010") cnt[2]++;
        elif(t == "011") cnt[3]++;
        elif(t == "100") cnt[4]++;
        elif(t == "101") cnt[5]++;
        elif(t == "110") cnt[6]++;
        elif(t == "111") cnt[7]++;
    }

    ll ansv = vmax(cnt);
    vll ans;
    rep(i,8) if(cnt[i] == ansv) ans.pb(i);

    rep(i,ans.size()){
        cout << ans[i];
        if(i == ans.size()-1) cout << endl;
        else cout << " ";
    }
    

}
0