結果
問題 |
No.313 π
|
ユーザー |
![]() |
提出日時 | 2015-12-06 15:54:41 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 18 ms / 5,000 ms |
コード長 | 1,622 bytes |
コンパイル時間 | 1,303 ms |
コンパイル使用メモリ | 159,896 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 15:21:47 |
合計ジャッジ時間 | 2,851 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef complex<double> P; typedef pair<int,int> pii; #define REP(i,n) for(ll i=0;i<n;++i) #define REPR(i,n) for(ll i=1;i<n;++i) #define FOR(i,a,b) for(ll i=a;i<b;++i) #define DEBUG(x) cout<<#x<<": "<<x<<endl #define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl #define ALL(a) (a).begin(),(a).end() #define MOD (ll)(1e9+7) #define ADD(a,b) a=((a)+(b))%MOD #define FIX(a) ((a)%MOD+MOD)%MOD #define MOD1 (MOD) #define MOD2 (MOD+2ll) #define BASE1 (ll)(1009) #define BASE2 (ll)(1007) #define FIX2(a) ((a)%MOD2+MOD2)%MOD2 ll myhash(string s,ll m,ll b){ ll ret = 0; REP(i,s.size()){ ret *= b; ret %= m; ret += s[i]; ret %= m; } return ret; } int main(){ string s; cin >> s; ll h1 = 904308214; ll h2 = 905431879; ll b1 = 1; ll b2 = 1; ll myhash1 = myhash(s,MOD1,BASE1); ll myhash2 = myhash(s,MOD2,BASE2); REP(_i,s.size()){ ll i = s.size()-1-_i; if(s[i]!='.'){ ll t = s[i]*b1%MOD1; ll h = (MOD1 + myhash1 - t)%MOD1; int cand = -1; REP(j,10){ if(s[i]==j+'0')continue; ll hh = (h+('0'+j)*b1)%MOD1; if(hh == h1){ cand = j; break; } } if(cand != -1){ t = s[i]*b2%MOD2; h = (MOD2+myhash2-t)%MOD2; ll hh = (h+('0'+cand)*b2)%MOD2; if(hh == h2){ cout << s[i] << " " << cand << endl; return 0; } } } b1 *= BASE1; b1 %= MOD1; b2 *= BASE2; b2 %= MOD2; } return 0; }