結果
問題 | No.381 名声値を稼ごう Extra |
ユーザー | IL_msta |
提出日時 | 2017-01-09 23:37:06 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 3,713 ms / 8,000 ms |
コード長 | 7,213 bytes |
コンパイル時間 | 606 ms |
コンパイル使用メモリ | 65,468 KB |
実行使用メモリ | 6,816 KB |
最終ジャッジ日時 | 2024-12-18 00:20:46 |
合計ジャッジ時間 | 4,893 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 3,713 ms
6,816 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; }