CSES - Datatähti 2017 alku - Results
Submission details
Task:Bittijono
Sender:ooh
Submission time:2016-10-04 14:17:39 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED19
#3ACCEPTED71
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.14 s2details
#3ACCEPTED0.23 s3details

Code

#include <iostream>
#include <cstdint>
#include <unistd.h>

using std::cout;
using std::endl;
using std::cin;

#define DEBUG false

uint64_t _2log(uint64_t x) {
  if (DEBUG) cout << "fastlog2: starting from " << x << endl;
  uint64_t res = 0;
  while (x >>= 1) {
    ++res;
    if (DEBUG) cout << "fastlog2: x=" << x << " res=" << res << endl;
    if (DEBUG) usleep(100000);
  }
  return res;
}

uint64_t _2pow(uint64_t x) {
  return (uint64_t)1 << x;
}

int main (int argc, char** argv) {
  uint64_t n;
  cin >> n;
  for (; n>0; --n) {
    uint64_t pos;
    cin >> pos;
    uint64_t i = 0;

    while (pos != 1) {
      if (DEBUG) cout << endl;
      uint64_t x = _2log(pos);
      if (DEBUG) cout << "fastpow2: result: " << _2pow(x) << endl ;
      uint64_t delta = pos - _2pow(x);
      if (DEBUG) cout << "x=" << x << " delta=" << delta << " pos=" << pos << endl;
      if (DEBUG) sleep(1);
      if (delta == 0) {
        i += x;
        goto out;
      } else {
        pos = delta;
      }

      i++;
    }
    out:
    cout << (i%2 == 0 ? "0" : "1") << endl;
  }

  return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
100
62
9
12
73
...

correct output
1
1
1
0
1
...

user output
1
1
1
0
1
...

Test 2

Group: 2

Verdict: ACCEPTED

input
100000
565433
141881
120108
825392
...

correct output
1
1
0
0
1
...

user output
1
1
0
0
1
...

Test 3

Group: 3

Verdict: ACCEPTED

input
100000
374768524402011755
937067109466254318
389256426086302899
932585725667010169
...

correct output
0
1
1
1
1
...

user output
0
1
1
1
1
...