結果
| 問題 |
No.1729 ～サンプルはちゃんと見て！～ 16進数と8進数(1)
|
| コンテスト | |
| ユーザー |
 Kyo_s_s
|
| 提出日時 | 2021-11-05 21:43:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 13,727 bytes |
| コンパイル時間 | 4,618 ms |
| コンパイル使用メモリ | 247,424 KB |
| 最終ジャッジ日時 | 2025-01-25 12:06:25 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 |
ソースコード
#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 << " ";
}
}