結果

問題 No.8005 天使のハッシュ関数
コンテスト
ユーザー TKTYI
提出日時 2022-08-12 00:55:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 4,283 bytes
コンパイル時間 4,424 ms
コンパイル使用メモリ 257,352 KB
最終ジャッジ日時 2025-01-30 20:17:39
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
#define FOR(i,l,r) for(ll i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,l,r) for(ll i=r-1;i>=l;i--)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define PA pair<ll,ll>
#define F first
#define S second
#define BS(A,x) binary_search(ALL(A),x)
#define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin())
#define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin())
#define COU(A,x) (UB(A,x)-LB(A,x))
#define sz(c) ((ll)(c).size())
/*
#include<boost/multiprecision/cpp_int.hpp>
namespace mp=boost::multiprecision;
using Bint=mp::cpp_int;
*/
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>&p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>&v){REP(i,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
ld dist(ld x1,ld y1,ld x2,ld y2){return sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
//using mint=modint1000000007;
using mint=modint998244353;
//const ll mod=1000000007;
const ll mod=998244353;
//using mint=modint;
ostream&operator<<(ostream&os,mint&a){os<<a.val();return os;}

unsigned leftRotate(unsigned x,int c){return (x<<c)|(x>>(32-c));}

char Hex(unsigned x){
  if(x<10)return '0'+x;
  else return 'a'+x-10;
}

string md5(string S){
  vector<bool>message;
  for(auto item:S){int c=item;REP(i,8)message.emplace_back((c>>i)%2);}
  vector<unsigned>s=
  {
   7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,
   5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,
   4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,
   6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21
  };

  const vector<unsigned>K=
  {
    0xD76AA478, 0xE8C7B756, 0x242070DB, 0xC1BDCEEE,
    0xF57C0FAF, 0x4787C62A, 0xA8304613, 0xFD469501,
    0x698098D8, 0x8B44F7AF, 0xFFFF5BB1, 0x895CD7BE,
    0x6B901122, 0xFD987193, 0xA679438E, 0x49B40821,
    0xF61E2562, 0xC040B340, 0x265E5A51, 0xE9B6C7AA,
    0xD62F105D, 0x02441453, 0xD8A1E681, 0xE7D3FBC8,
    0x21E1CDE6, 0xC33707D6, 0xF4D50D87, 0x455A14ED,
    0xA9E3E905, 0xFCEFA3F8, 0x676F02D9, 0x8D2A4C8A,
    0xFFFA3942, 0x8771F681, 0x6D9D6122, 0xFDE5380C,
    0xA4BEEA44, 0x4BDECFA9, 0xF6BB4B60, 0xBEBFBC70,
    0x289B7EC6, 0xEAA127FA, 0xD4EF3085, 0x04881D05,
    0xD9D4D039, 0xE6DB99E5, 0x1FA27CF8, 0xC4AC5665,
    0xF4292244, 0x432AFF97, 0xAB9423A7, 0xFC93A039,
    0x655B59C3, 0x8F0CCC92, 0xFFEFF47D, 0x85845DD1,
    0x6FA87E4F, 0xFE2CE6E0, 0xA3014314, 0x4E0811A1,
    0xF7537E82, 0xBD3AF235, 0x2AD7D2BB, 0xEB86D391
  };
  
  unsigned a0=0x67452301;
  unsigned b0=0xEFCDAB89;
  unsigned c0=0x98BADCFE;
  unsigned d0=0x10325476;
  
  unsigned long long initial_message_length=message.size();
  
  REP(i,7)message.emplace_back(0);
  message.emplace_back(1);
  
  do{message.emplace_back(0);}while(sz(message)%512!=448);
  REP(i,64)message.emplace_back((initial_message_length>>i)%2);
  
  REP(_,sz(message)/512){
    vector<bool>chunk{message.begin()+512*_,message.begin()+512*(_+1)};
    vector<unsigned>M(16);REP(i,16)REP(j,32)M[i]+=chunk[32*i+j]<<j;
    unsigned A=a0;
    unsigned B=b0;
    unsigned C=c0;
    unsigned D=d0;
    unsigned F;
    int g;
    REP(i,64){
      if(i<16){F=D^(B&(C^D));g=i;}
      else if(i<32){F=C^(D&(B^C));g=(5*i+1)%16;}
      else if(i<48){F=B^C^D;g=(3*i+5)%16;}
      else{F=C^(B|~D);g=7*i%16;}
      F+=A+K[i]+M[g];
      A=D;D=C;C=B;
      B+=leftRotate(F,s[i]);
    }
    a0+=A;
    b0+=B;
    c0+=C;
    d0+=D;
  }
  string res;
  REP(i,8){res+=Hex(a0%16);a0/=16;}
  REP(i,8){res+=Hex(b0%16);b0/=16;}
  REP(i,8){res+=Hex(c0%16);c0/=16;}
  REP(i,8){res+=Hex(d0%16);d0/=16;}
  REP(i,sz(res))if(i%2==0)swap(res[i],res[i+1]);
  return res;
}

int main(){
  string S;cin>>S;
  //cout<<md5(S)<<endl;
  cout<<md5(md5(S))<<endl;
  return 0;
}
0