50097. Conveyor Belt

I'm a slow walker, but I never walk backwards.

Task Description

You are given $N$ integers to represent a circular conveyor belt of $64N$ bits in length. Each bit of the integers represents whether there is a packet on the belt or not. In every second, the belt moves to the left (the most significant bit) by one bit, and the leftmost bit of the left most integer is moved to the rightmost bit (the least significant bit) of the rightmost integer because the belt is circular. Write a function to determine the conveyor belt status after $T$ seconds.

We illustrate the rotation by an example. Let $N$ be 2 and the integer sequence be {2017, -1121}. Initially ($T$ = 0) the conveyor belt is like this.

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0111 1110 0001

1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1011 1001 1111

After 10 seconds ($T$= 10) the conveyor belt will be like this, and the integer sequence becomes {2066431, -1147904}.

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1111 1000 0111 1111 1111

1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110 1110 0111 1100 0000 0000

After 64 seconds ($T$ = 64) the conveyor belt will be like this, and the integer sequence becomes {-1121, 2017}.

1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1011 1001 1111

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0111 1110 0001

Finally after 100 seconds ($T$ = 100) the conveyor belt is like this, and the integer sequence becomes {-77034533421056, 138675904053247}.

1111 1111 1111 1111 1011 1001 1111 0000 0000 0000 0000 0000 0000 0000 0000 0000

0000 0000 0000 0000 0111 1110 0001 1111 1111 1111 1111 1111 1111 1111 1111 1111

You may use the following main function to test your function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include"transmission.h"
#define MAXSIZE 1048576
long long int belt[MAXSIZE];
int main(){
    int N,T;
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++)
        scanf("%lld",&belt[i]);
    transmission(belt,N,T);
    for(int i=0;i<N;i++)
        printf("%lld%s",belt[i],i==N-1?"":" ");
    return 0;
}

The prototype of transmission function you need to implement is as follows.

1
void transmission(long long int belt[],int N,int T);

The transmission.h is as follow:

1
void transmission(long long int belt[],int N,int T);

Subtask

  • 10 points: $T=0$.
  • 10 points: $T$ is a multiple of 64 and no more than $64N$.
  • 60 points: $1 \leq T \leq 63$.
  • 20 points: $T \leq 64N$.

Input Format

The input contains only one test case. The first line contains two integers $N$ and $T$, where $N$ is the element number of the integer sequence, and $T$ is the time number. The second line contains $N$ integers, and the $i$-th integer represents $i$-th element of the integer sequence.

  • $N \leq 1048576$.

Output Format

Print the result integer sequence in a line.

Sample Input 1

2 64
2017 -1121

Sample Output 1

-1121 2017

Sample Input 2

2 10
2017 -1121

Sample Output 2

2066431 -1147904

Sample Input 3

2 100
2017 -1121

Sample Output 3

-77034533421056 138675904053247

Compile

gcc -std=c99 -O2 -c main.c -lm
gcc -std=c99 -O2 -c transmission.c -lm
gcc -std=c99 -O2 transmission.o main.o -lm

Discussion