結果
| 問題 | No.381 名声値を稼ごう Extra |
| ユーザー |
 IL_msta
|
| 提出日時 | 2017-01-09 23:37:06 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 3,987 ms / 8,000 ms |
| コード長 | 7,213 bytes |
| コンパイル時間 | 529 ms |
| コンパイル使用メモリ | 65,844 KB |
| 実行使用メモリ | 6,940 KB |
| 最終ジャッジ日時 | 2024-05-10 03:29:40 |
| 合計ジャッジ時間 | 4,904 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 3,987 ms
6,940 KB |
コンパイルメッセージ
main.cpp:177:7: warning: extra tokens at end of #else directive [-Wendif-labels]
177 | #else __MyNumBig__
| ^~~~~~~~~~~~
ソースコード
//#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;
}