結果

問題 No.381 名声値を稼ごう Extra
コンテスト
ユーザー IL_msta
提出日時 2017-01-12 09:50:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 5,603 ms / 8,000 ms
コード長 7,049 bytes
コンパイル時間 747 ms
コンパイル使用メモリ 99,252 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 10:08:02
合計ジャッジ時間 6,740 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>

#include <sstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include<cassert>//assert();
#include <fstream>
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
#ifdef getchar_unlocked
#define mygc(c) (c)=getchar_unlocked()
#else
#define mygc(c) (c)=getchar()
#endif
#ifdef putchar_unlocked
#define mypc(c) putchar_unlocked(c)
#else
#define mypc(c) putchar(c)
#endif
/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
/////////
using namespace::std;
/////////
/////数値読み込み
#define ENABLE_READER_ON(T)	\
inline void reader(T &x){\
	int k;x = 0;bool flag = true;\
	while(true){\
		mygc(k);\
		if( k == '-'){\
			flag = false;break;\
		}\
		if('0' <= k && k <= '9'){\
			x = k - '0';break;\
		}\
	}\
	if( flag ){\
		while(true){\
			mygc(k);\
			if( k<'0' || '9'<k)break;\
			x = x * 10 + (k - '0');\
		}\
	}else{\
		while(true){\
			mygc(k);\
			if( k<'0' || '9'<k)break;\
			x = x * 10 - (k-'0');\
		}\
	}\
}
//整数
ENABLE_READER_ON(int)
ENABLE_READER_ON(long)
ENABLE_READER_ON(long long)
ENABLE_READER_ON(unsigned int)
ENABLE_READER_ON(unsigned long)
ENABLE_READER_ON(unsigned long long)

//////
//文字読み込み
inline int reader(char c[]){int i,s=0;
for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}
c[s++]=i;
for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}
c[s]='\0';return s;
}

inline int reader(string& c,int size=100){int i;c.reserve(size);
for(;;){mygc(i);if(i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF)break;}
c.push_back(i);
for(;;){mygc(i);if(i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF)break;c.push_back(i);}
return c.size();}

/////////
//数値出力
#define ENABLE_WRITER_ON(T)	\
inline void writer(T x){char f[20];int s = 0;\
if (x<0){mypc('-');while(x){f[s++] = ~(x%10)+1,x /= 10;}}\
else{while(x){f[s++] = (x % 10), x /= 10;}}\
if (!s)f[s++] = 0;while (s--)mypc(f[s] + '0');}

ENABLE_WRITER_ON(int)
ENABLE_WRITER_ON(long)
ENABLE_WRITER_ON(long long)
ENABLE_WRITER_ON(unsigned int)
ENABLE_WRITER_ON(unsigned long)
ENABLE_WRITER_ON(unsigned long long)
/////////
inline void writer(const char c[]){for (int i = 0; c[i] != '\0'; i++)mypc(c[i]); }
inline void writer(const string str){writer( str.c_str() );}
/////////
/*

*/
ULL popcount(ULL N){
	N -=  (N >> 1) & 0x5555555555555555ULL;
	N  = ((N >> 2) & 0x3333333333333333ULL) + (N & 0x3333333333333333ULL);
	N  = ((N >> 4) + N) & 0x0F0F0F0F0F0F0F0FULL;
	return (N * 0x0101010101010101ULL) >> 56;
}

/*
CPythonのソース参照
longobject.c

以下は
*/
const int PyLong_SHIFT (30);
//#define PyLong_SHIFT (15)
const unsigned long long PyLong_BASE	((ULL)1<<PyLong_SHIFT);
const unsigned long long PyLong_MASK ((ULL)PyLong_BASE-1);

//#define __MyNumBig__ __MyNumBig__
/*
PyObject *
PyLong_FromString(const char *str, char **pend, int base);
*/
//ﾃﾞﾌｫﾙﾄ 10進数が来る事を想定
unsigned long long to_num(char* str,int base=10){
/////数値を読み込むときに基数変換しておく
	/*
	元の数値の基数		base
	変換後の数値の基数	BASE
	*/
	//変換後の桁数=配列数。多倍長にしないと真に多倍長にはなれない。
	unsigned long long size_z;
	unsigned long long digits;//受け取った。桁数=文字数
	//1文字で1桁を想定。36進数まで
	int convwidth;
    unsigned long long convmultmax, convmult;//元の型はtwodigits

	static double log_base_BASE[37];
	log_base_BASE[0] = (double)(0.0e0);
	static int convwidth_base[37];
	convwidth_base[0] = 0;
	static unsigned long long convmultmax_base[37];
	convmultmax_base[0] = 0;//

	if( log_base_BASE[base] == 0.0){
		//一度だけ計算する。staticに結果は保存される。
		//基数変換による桁数決定に使用。
		//AB -> A*base^1 +b*base^0
		unsigned long long convmax = base;
		int i= 1;
		log_base_BASE[base] =(log((double)base)/
							  log((double)PyLong_BASE));
		for(;;){
			unsigned long long next = convmax * base;
			//PyLong_BASE進数
			if( next > PyLong_BASE ){
				break;
			}
			convmax = next;
			++i;
		}
		convmultmax_base[base] = convmax;
		assert(i>0);
		convwidth_base[base] = i;//桁数保存
	}
	/*
	log_base_BASE[10]		= 0.110731
	convmultmax_base[10]	= 10^9
	convwidth_base[10]		= 9
	*/
//文字列の長さは取得できる。
	digits = strlen(str);
//必要な容量の計算
	size_z = (unsigned long long)(digits * log_base_BASE[base]) + 1;
	vector<unsigned long long> z((unsigned int)size_z,0);//上限unsigned int

	convwidth = convwidth_base[base];
	convmultmax = convmultmax_base[base];

	/* Work (^o^)*///かわいい顔文字をここへ
	unsigned long long calNum;
	const int len = strlen(str);
	int pos,posMax;//
	posMax = 0;//値を格納してるMaxIndex...名前
	
	int strPos = 0;//strの位置
	while(strPos<len){
		calNum = 0;
		for(pos=0; pos < convwidth && strPos < len;++pos){
			//元では文字変換テーブル(_PyLong_DigitValue[])を通している。
			//ここでは10進数だけを想定している。
			//ここでは確実に数値だけの文字列を想定している。
			calNum = calNum * base + str[strPos] - '0';
			++strPos;
			assert(calNum < PyLong_BASE);
		}
		convmult = convmultmax;//初期化
		if( pos != convwidth ){//欲しい桁なかった=最後の部分
			convmult = base;
			for( ; pos > 1;--pos){
				convmult *= base;
			}
		}
		
		//z[]に値を入れていく。0初期化
		/*
		元ソースのコメントにある
		(((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
		括弧の一番奥から計算していく、最後は調整のため掛けるBも合わせてる。
		*/
		for(pos = 0; pos < posMax+1;++pos){
			calNum += z[pos] * convmult;
			z[pos] = calNum & PyLong_MASK;
			calNum >>= PyLong_SHIFT;
		}

		//繰り上がりの処理、1loop1回は来る。
		if(calNum){//頻繁に来る
			assert(calNum < PyLong_BASE);
			//次の桁に入れる。
			if( (unsigned)pos >= z.size() ){//容量不足
				z.push_back( calNum );
			}else{
				z[pos] = calNum;//容量の不安はある
			}
			posMax = max(posMax,pos);
		}
	}
	unsigned long long ret = 0;
	int i=0;
	const ULL sizeMax = z.size();
	for(i=0; i<sizeMax; ++i){
		ret += popcount(z[i]);
	}
	/*
	cout << "[" << ret << "]" << endl;
	cout << "posMax\t" << posMax << endl;
	cout << "z.size()\t" <<z.size() << endl;
	cout << "z[z.size()-1]\t" << z[z.size()-1] << endl;
	*/
	return ret;
}

inline void solve(){
	char str[1000002];
	reader(str);
	writer( to_num(str) );
}

int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//小数を10進数表示
    //cout << setprecision(16);//小数をいっぱい表示する。16?
	
	solve();
	return 0;
}
0