#214540 (C++11) No.589 Counting Even

提出ソース

結果

問題	No.589 Counting Even
ユーザー	manugino
提出日時	2017-11-04 18:17:00
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	6,678 bytes
コンパイル時間	753 ms
コンパイル使用メモリ	85,144 KB
実行使用メモリ	13,696 KB
最終ジャッジ日時	2024-11-23 18:05:43
合計ジャッジ時間	57,800 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 9,760 KB
testcase_01	AC	2 ms 8,320 KB
testcase_02	AC	2 ms 9,892 KB
testcase_03	AC	2 ms 8,320 KB
testcase_04	AC	2 ms 10,624 KB
testcase_05	AC	2 ms 8,320 KB
testcase_06	AC	4 ms 10,624 KB
testcase_07	AC	135 ms 6,820 KB
testcase_08	AC	1,798 ms 10,624 KB
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	AC	2 ms 10,624 KB
testcase_23	AC	2 ms 8,320 KB
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-

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

ソースコード

raw source code

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [Tips]
// XCodeでのEOF入力はCtrl+D
// ¥はAlt+\
// ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////




////////////////////////////////////////
//yukicorder
//
////////////////////////////////////////


//#define debug //*******************************************************************************************************************************************
#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter
#include <set>


//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを.
//#define INPUTFILE "input.txt" //**************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scand(A) scanf("%d", &(A))
#define scans(A) scanf("%s", (A))
#define printd(A) printf("%d\n", (A))
#define prints(A) printf("%s\n", (A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl
#define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl


#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) ((i)/2)
#define l(i) ((i)*2)
#define r(i) ((i)*2+1)
#define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16)
#define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1
#define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0

int dx[] = {1, 0, -1,  0};
int dy[] = {0, 1,  0, -1};

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

//const int INF = (1LL<<31)-1;
const int NONE = -1;
//const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
//const ull INF_ULL = (ull)1e19-1ULL;
//#define MOD 1000000007 //大きい素数の代表といえばこの人、10億7さん

#define N_MAX 110 //num of vertex or element
//#define M_MAX 124760 //num of edge
//#define DATA_MAX 1010

int C[N_MAX][N_MAX] = {0};

ll N;


void init() {
#ifdef debug
    C[0][0] = 1;
    rep(i,1,N+1) {
        rep(j,0,N+1) {
            C[i][j] = (j-1<0 ? 0 : C[i-1][j-1]) + C[i-1][j];
        }
    }
#endif
}



void display() {
#ifdef debug
    int even;
    int odd;
    
    dout << "----\n";
    dout << "   r = ";
    rep(j,0,N+1) dout << setw(5) << (j) << " ";
    dout << " :  odd even\n";
    rep(i,0,N+1) {
        even = odd = 0;
        
        disP(i); dout << " : ";
        rep(j,0,N+1) {
            if( C[i][j]%2==0 )
                dout << setw(5) << C[i][j] << " ";
            else
                dout << setw(5) << C[i][j] << "*";
                
            if(0<=j and j<=i) {
                if( C[i][j]%2==0 ) even++;
                else if( C[i][j]%2==1 ) odd++;
            }
        }
        dout << " : ";
        disP(odd);
        disP(even);
        dout << " N=" << static_cast<std::bitset<8> >(i) << ", " << __builtin_popcount(i);
        
        dout << endl;
    }
    
    
#endif
}



ll func(ll x) {
    
    ll a = 0;
    for(; x>0; x>>=1) {
        if((x&1)==0) a++;
        else break;
    }
    
    return a;
}





int main() {
    
    //cin, coutの高速化  ＊注意：cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように！
    cin.tie(0); //cinとcoutの同期を切る
    ios::sync_with_stdio(false); //iostreamとstdioの同期を切る
    
    //read input data
//    scand(N);
    
   
    din >> N;

    
    init();
    display();
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
#endif
    //------------------------------------------------------------------------------------------
    
    
   
    ll ans = 0;
    ll a = 0, c = 0;
    for(ll k=1; k<=N/2; k++) {
       
        a+=func(N+1-k);
        c+=func(k);
        
        if(a>c) ans++;
     
#ifdef debug
        dout << "-------------\n";
        disp(k);
        dout << endl;
        
        disp(N+1-k);
        disp(k);
        dout << endl;
        
        disp(func(N+1-k));
        disp(func(k));
        dout << endl;
        
        disp(a);
        disp(c);
        dout << endl;
        
    disp(ans);
#endif
        }
    
    ans *= 2;
    
    if(N%2==0) { //need to check N/2
        if(a>c) ans--;
         
#ifdef debug
        dout << "N%2==0\n";
        
        disp(a);
        disp(c);
        dout << endl;
        
        disp(ans);
#endif
        
    }
    
    dout << ans << endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}

yukicoder

結果

テストケース

ソースコード