Solution Idea

50057. Consecutive 0's and 1's

用 bit 運算可以快速的一個整數中某個位置的 bit 值 。例如要得到 $x$ 第 $i$ 個 bit ,可以先把 $x$ 向右 shift $i$ 次,再 and $1$ 。

1
2
int getIthSignificantBit(int x, int i)
    return (x >> i) & 1;

範例程式說明:
不需要把所有數字都存起來,只要用變數 pre 去記目前的 sequence 是 0 還是 1,並用 cnt 記得現在看到第幾個 bit。
每看一個 bit,若和 pre 相同就直接輸出;若不同代表 sequence 改變了,此時換行並輸出 (cnt % 40) 個空白,再輸出看到的 bit。

Judge status 說明:

  • OLE (Output Limit Exceeded): 輸出太多東西了
  • MLO (Memory Limit Exceeded): 用太多 memory 了
#include <stdio.h>
 
int main(){
    int N;
    scanf("%d", &N);
 
    int cnt = 0, preb, n;
    for(int i = 0; i < N; i++){
        scanf("%d", &n);
        if (i == 0) preb = (n >> 31) & 1; // first bit, initial
        for (int j = 31; j >= 0; j--){
            int b = (n >> j) & 1; // get j-th significant bit of n
            if (b != preb){ // if the sequence changes -> print a newline char and spaces
                printf("\n");
                for(int k = 0; k < cnt % 40; k++) printf(" ");
            }
            printf("%d", b);
            preb = b, cnt++;
        }
    }
    printf("\n");
    return 0;
}

Discussion