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

提出ソース

結果

問題	No.381 名声値を稼ごう Extra
ユーザー	IL_msta
提出日時	2017-01-09 23:37:06
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	4,339 ms / 8,000 ms
コード長	7,213 bytes
コンパイル時間	857 ms
コンパイル使用メモリ	66,264 KB
実行使用メモリ	5,444 KB
最終ジャッジ日時	2023-08-22 21:55:28
合計ジャッジ時間	5,676 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	4,339 ms 5,444 KB

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

コンパイルメッセージ

main.cpp:177:7: warning: extra tokens at end of #else directive [-Wendif-labels]
 #else __MyNumBig__
       ^~~~~~~~~~~~

ソースコード

raw source code

//#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>

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

#include <string>
//#include <vector>
//#include <valarray>

/*
#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>
/////////
//#define mygc(c) (c)=getchar_unlocked()
/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
/////////
using namespace::std;
/////////
int reader(char c[]){
	int i,s=0;
	for(;;){
		//mygc(i);
		//i = getchar_unlocked();
		i = getchar();
		if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;
	}c[s++]=i;
	for(;;){
		//mygc(i);
		//i = getchar_unlocked();
		i = getchar();
		if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;
		c[s++]=i;
	}c[s]='\0';return s;
}
/////////
#define ketaMax 19
/*
(上の桁の余り*10^N)>>Nが値に収まるか
(1<<N-1 * (10^N>>N) )
18446744073709551615 = unsigned __int64__ MAX
10^N					N	10^N>>N					1<<N-1	18446744073709551615(*)
10000000000000000000	19	19073486328125	1<<19-1	524287	9999980926513671875
 1000000000000000000	18	3814697265625	1<<18-1	262143	999996185302734375
  100000000000000000	17	762939453125	1<<17-1	131071	99999237060546875
   10000000000000000	16	152587890625	1<<16-1	65535	9999847412109375
    1000000000000000	15	30517578125		1<<15-1	32767	999969482421875
     100000000000000	14	6103515625		1<<14-1	16383	99993896484375
      10000000000000	13	1220703125		1<<13-1	8191	9998779296875
       1000000000000	12	244140625		1<<12-1	4095	999755859375
*/

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

//#define __MyNumBig__ __MyNumBig__
int to_num(ULL* ans, string& str){
	const int len = str.length();
	const int Q = len/ketaMax;
	const int R = len%ketaMax;
	int strPos = 0;
	ULL val = 0;

#ifndef __MyNumBig__
	//
	//ans[0]が一番小さい
	//
	if(R){//桁余り部分があるなら
		for(;strPos<R;++strPos){
			val = val*10 + str[strPos]-'0';
		}
		ans[Q] = val;
	}
	for(int i=0;i<Q;++i){//Q要素分
		val = 0;
		for(int j=0;j<ketaMax;++j){
			val = val*10 + str[R + i*ketaMax+j]-'0';
		}
		ans[Q-i-1] = val;
	}
	ans[Q+1] = 0;//A[i]= A[i] + A[i+1] ループ用
	return Q+1;//使用した要素数を返す
#else
	//
	//ans[0]が一番大きい
	//
	if(R){//桁余り部分があるなら
		for(;strPos<R;++strPos){
			val = val*10 + str[strPos]-'0';
		}
		ans[0] = val;
	}
	for(int i=0;i<Q;++i){//Q要素分
		val = 0;
		for(int j=0;j<ketaMax;++j){
			val = val*10 + str[R + i*ketaMax+j]-'0';
		}
		ans[i+(R!=0)] = val;
	}
	return Q+1;//使用した要素数を返す
#endif
}

struct vnum{
	ULL num[1000000/ketaMax + 2];//

	int len;
	static const ULL powMax		= (ULL)19073486328125;//(10^19)>>19
	static const ULL divMask	= (ULL)0x7FFFF;//524287
	static const int divShift	= 19;

	void set(string str){
		len = to_num(num, str);
	}

	void div(){//
		ULL ans = 0;
		ULL ama = 0;
		
#ifndef __MyNumBig__
		//num[0]一番小さい
		while( len ){
			ans += popcount( num[0] & divMask );//
			long i;
			for(i=0; i < len-0;i+=1){//
num[i+ 0] =  ( (num[i+ 0]) >> 19 ) + (num[i+ 1] & 524287) * (ULL)19073486328125;//商
/*num[i+ 1] =  ( (num[i+ 1]) >> 19 ) + (num[i+ 2] & 524287) * (ULL)19073486328125;
num[i+ 2] =  ( (num[i+ 2]) >> 19 ) + (num[i+ 3] & 524287) * (ULL)19073486328125;
num[i+ 3] =  ( (num[i+ 3]) >> 19 ) + (num[i+ 4] & 524287) * (ULL)19073486328125;
num[i+ 4] =  ( (num[i+ 4]) >> 19 ) + (num[i+ 5] & 524287) * (ULL)19073486328125;
num[i+ 5] =  ( (num[i+ 5]) >> 19 ) + (num[i+ 6] & 524287) * (ULL)19073486328125;
num[i+ 6] =  ( (num[i+ 6]) >> 19 ) + (num[i+ 7] & 524287) * (ULL)19073486328125;
num[i+ 7] =  ( (num[i+ 7]) >> 19 ) + (num[i+ 8] & 524287) * (ULL)19073486328125;

num[i+ 8] =  ( (num[i+ 8]) >> 19 ) + (num[i+ 9] & 524287) * (ULL)19073486328125;
num[i+ 9] =  ( (num[i+ 9]) >> 19 ) + (num[i+10] & 524287) * (ULL)19073486328125;
num[i+10] =  ( (num[i+10]) >> 19 ) + (num[i+11] & 524287) * (ULL)19073486328125;
num[i+11] =  ( (num[i+11]) >> 19 ) + (num[i+12] & 524287) * (ULL)19073486328125;
num[i+12] =  ( (num[i+12]) >> 19 ) + (num[i+13] & 524287) * (ULL)19073486328125;
num[i+13] =  ( (num[i+13]) >> 19 ) + (num[i+14] & 524287) * (ULL)19073486328125;
num[i+14] =  ( (num[i+14]) >> 19 ) + (num[i+15] & 524287) * (ULL)19073486328125;
num[i+15] =  ( (num[i+15]) >> 19 ) + (num[i+16] & 524287) * (ULL)19073486328125;
*/
			}//要素数を一つ増やして0を入れておく
			/*for(; i < len;++i){
num[i+0] =  ( (num[i+0]) >> 19 ) + (num[i+1] & 524287) * (ULL)19073486328125;//
			}
			*/
			//上の要素が0になっていく。
			len -= num[len-1] == 0;
		}
		///////////////
#else __MyNumBig__
		//num[0]一番大きい
		int start = 0;
		ULL ama2;
		while( start < len ){
			long i;
			ama = 0;
			ama2 = 0;
			for(i=start ; i < len-15;i+=16){//
		ama2	= num[i+ 0] & divMask;
		num[i+0]	= ( (num[i+ 0]) >> divShift ) + ama * powMax;

		ama	= num[i+ 1] & divMask;
		num[i+1]	= ( (num[i+ 1]) >> divShift ) + ama2 * powMax;

		ama2	= num[i+ 2] & divMask;
		num[i+2]	= ( (num[i+ 2]) >> divShift ) + ama * powMax;

		ama	= num[i+ 3] & divMask;
		num[i+3]	= ( (num[i+ 3]) >> divShift ) + ama2 * powMax;

		ama2	= num[i+ 4] & divMask;
		num[i+4]	= ( (num[i+ 4]) >> divShift ) + ama * powMax;

		ama	= num[i+ 5] & divMask;
		num[i+5]	= ( (num[i+ 5]) >> divShift ) + ama2 * powMax;

		ama2	= num[i+ 6] & divMask;
		num[i+6]	= ( (num[i+ 6]) >> divShift ) + ama * powMax;

		ama	= num[i+ 7] & divMask;
		num[i+7]	= ( (num[i+ 7]) >> divShift ) + ama2 * powMax;

		ama2	= num[i+ 8] & divMask;
		num[i+8]	= ( (num[i+ 8]) >> divShift ) + ama * powMax;

		ama	= num[i+ 9] & divMask;
		num[i+9]	= ( (num[i+ 9]) >> divShift ) + ama2 * powMax;

		ama2	= num[i+ 10] & divMask;
		num[i+10]	= ( (num[i+ 10]) >> divShift ) + ama * powMax;

		ama	= num[i+ 11] & divMask;
		num[i+11]	= ( (num[i+ 11]) >> divShift ) + ama2 * powMax;

		ama2	= num[i+ 12] & divMask;
		num[i+12]	= ( (num[i+ 12]) >> divShift ) + ama * powMax;

		ama	= num[i+ 13] & divMask;
		num[i+13]	= ( (num[i+ 13]) >> divShift ) + ama2 * powMax;

		ama2	= num[i+ 14] & divMask;
		num[i+14]	= ( (num[i+ 14]) >> divShift ) + ama * powMax;

		ama	= num[i+ 15] & divMask;
		num[i+15]	= ( (num[i+ 15]) >> divShift ) + ama2 * powMax;
		
			}
			for(; i < len;++i){
		ama2	= num[i] & divMask;
		num[i]	= ( (num[i]) >> divShift ) + ama * powMax;
		ama		= ama2;
			}
			ans += popcount( ama );//
			//上の要素が0になっていく。
			start += num[start] == 0;
		}
#endif
		///////////////
		cout << ans << endl;
	}
};

//string str(1000000,'0');
char str[1000002];
vnum Num;
void solve(){	
	//str.reserve(1000000);
	reader(str);
	//cin >> str;

	Num.set(str);
	Num.div();
}

int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(16);//
	
	solve();
	
	return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード