#144133 (C++11) No.381 名声値を稼ごう Extra

提出ソース

結果

問題	No.381 名声値を稼ごう Extra
ユーザー	IL_msta
提出日時	2017-01-12 10:29:44
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	6,710 bytes
コンパイル時間	1,305 ms
コンパイル使用メモリ	98,016 KB
実行使用メモリ	8,368 KB
最終ジャッジ日時	2023-08-23 08:42:39
合計ジャッジ時間	10,895 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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進数が来る事を想定
void to_num(){
	const int base = 10;
/////数値を読み込むときに基数変換しておく
	/*
	元の数値の基数		base
	変換後の数値の基数	BASE
	*/
    unsigned long long 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
	*/
//文字列の長さは取得できる。

//必要な容量の計算
	//size_z = (unsigned long long)(digits * log_base_BASE[base]) + 1;

	vector<unsigned long long> z(110731,0);//上限unsigned int

	const int convwidth = 9;//convwidth_base[base];
	ULL convmultmax = 1000000000;//convmultmax_base[base];

	/* Work (^o^)*///かわいい顔文字をここへ
	unsigned long long calNum;
	int pos,posMax;//
	posMax = 0;//値を格納してるMaxIndex...名前
	
	int strPos = 0;//strの位置
	int str;
	convmult = convmultmax;//初期化,最後だけ変わる。
	bool flag = true;
	while(flag){
		calNum = 0;
		
		for(pos=0; pos < convwidth; ++pos){
			//元では文字変換テーブル(_PyLong_DigitValue[])を通している。
			//ここでは10進数だけを想定している。
			//ここでは確実に数値だけの文字列を想定している。
			str = getchar();
			if( str < '0' || '9' < str ){
				--pos;
				flag = false;
				break;
			}
			calNum = calNum * base + str - '0';
			assert(calNum < PyLong_BASE);
		}
		
		if( flag == false && pos < 0){
			break;
		}
		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も合わせてる。
		*/
		++posMax;
		for(pos = 0; pos < posMax;++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);
		}
		if( str < '0' || '9' < str ) break;
	}

	unsigned long long ret = 0;
	for(int i=0; i<posMax; ++i){
		ret += popcount(z[i]);
	}
	writer(ret);
	return;
}

inline void solve(){
	to_num();
}

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;
}

yukicoder

結果

テストケース

ソースコード