Perfect Triples (Codeforces 1339E)
Tags: Math, bitmasks

Consider the infinite sequence $$$s$$$ of positive integers, created by repeating the following steps:  Find the lexicographically smallest triple of positive integers $$$(a, b, c)$$$ such that   $$$a \oplus b \oplus c = 0$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.  $$$a$$$, $$$b$$$, $$$c$$$ are not in $$$s$$$.  Here triple of integers $$$(a_1, b_1, c_1)$$$ is considered to be lexicographically smaller than triple $$$(a_2, b_2, c_2)$$$ if sequence $$$[a_1, b_1, c_1]$$$ is lexicographically smaller than sequence $$$[a_2, b_2, c_2]$$$.  Append $$$a$$$, $$$b$$$, $$$c$$$ to $$$s$$$ in this order.  Go back to the first step. You have integer $$$n$$$. Find the $$$n$$$-th element of $$$s$$$.You have to answer $$$t$$$ independent test cases.A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ if in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.Each of the next $$$t$$$ lines contains a single integer $$$n$$$ ($$$1\le n \le 10^{16}$$$) — the position of the element you want to know.

Output: In each of the $$$t$$$ lines, output the answer to the corresponding test case.

Note: The first elements of $$$s$$$ are $$$1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $$$

Sample Inputs:
9
1
2
3
4
5
6
7
8
9

Sample Outputs:
1
2
3
4
8
12
5
10
15

Solution (Python):
import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
partial = [1, 2, 3, 4, 8, 12, 5, 10, 15, 6, 11, 13, 7, 9, 14, 16, 32, 48, 17, 34, 51, 18, 35, 49, 19, 33, 50, 20, 40, 60, 21, 42, 63, 22, 43, 61, 23, 41, 62, 24, 44, 52, 25, 46, 55, 26, 47, 53, 27, 45, 54, 28, 36, 56, 29, 38, 59, 30, 39, 57, 31, 37, 58, 64, 128, 192, 65, 130, 195, 66, 131, 193, 67, 129, 194, 68, 136, 204, 69, 138, 207, 70, 139, 205, 71, 137, 206, 72, 140, 196, 73, 142, 199, 74, 143, 197, 75, 141, 198, 76, 132, 200, 77, 134, 203, 78, 135, 201, 79, 133, 202, 80, 160, 240, 81, 162, 243, 82, 163, 241, 83, 161, 242, 84, 168, 252, 85, 170, 255, 86, 171, 253, 87, 169, 254, 88, 172, 244, 89, 174, 247, 90, 175, 245, 91, 173, 246, 92, 164, 248, 93, 166, 251, 94, 167, 249, 95, 165, 250, 96, 176, 208, 97, 178, 211, 98, 179, 209, 99, 177, 210, 100, 184, 220, 101, 186, 223, 102, 187, 221, 103, 185, 222, 104, 188, 212, 105, 190, 215, 106, 191, 213, 107, 189, 214, 108, 180, 216, 109, 182, 219, 110, 183, 217, 111, 181, 218, 112, 144, 224, 113, 146, 227, 114, 147, 225, 115, 145, 226, 116, 152, 236, 117, 154, 239, 118, 155, 237, 119, 153, 238, 120, 156, 228, 121, 158, 231, 122, 159, 229, 123, 157, 230, 124, 148, 232, 125, 150, 235, 126, 151, 233, 127, 149, 234, 256, 512, 768]
for t in range(T):
    n = int(lines[t + 1].strip())
    if n <= 255:
        print(partial[n - 1])
        continue
    index = n % 3
    lowPow4 = 4 ** (len(bin(n)[3:]) // 2)
    first = lowPow4 + (n - lowPow4) // 3
    tmp = [0, 2, 3, 1]

    def theSecond(fi):
        if fi < 128:
            j = partial.index(fi)
            return partial[j + 1]
        prev = theSecond(fi // 4)
        return prev * 4 + tmp[fi % 4]
    second = theSecond(first)
    if index == 1:
        print(first)
    elif index == 2:
        print(second)
    else:
        print(first ^ second)

Solution (Python):
import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
partial = [1, 2, 3, 4, 8, 12, 5, 10, 15, 6, 11, 13, 7, 9, 14, 16, 32, 48, 17, 34, 51, 18, 35, 49, 19, 33, 50, 20, 40, 60, 21, 42, 63, 22, 43, 61, 23, 41, 62, 24, 44, 52, 25, 46, 55, 26, 47, 53, 27, 45, 54, 28, 36, 56, 29, 38, 59, 30, 39, 57, 31, 37, 58, 64, 128, 192, 65, 130, 195, 66, 131, 193, 67, 129, 194, 68, 136, 204, 69, 138, 207, 70, 139, 205, 71, 137, 206, 72, 140, 196, 73, 142, 199, 74, 143, 197, 75, 141, 198, 76, 132, 200, 77, 134, 203, 78, 135, 201, 79, 133, 202, 80, 160, 240, 81, 162, 243, 82, 163, 241, 83, 161, 242, 84, 168, 252, 85, 170, 255, 86, 171, 253, 87, 169, 254, 88, 172, 244, 89, 174, 247, 90, 175, 245, 91, 173, 246, 92, 164, 248, 93, 166, 251, 94, 167, 249, 95, 165, 250, 96, 176, 208, 97, 178, 211, 98, 179, 209, 99, 177, 210, 100, 184, 220, 101, 186, 223, 102, 187, 221, 103, 185, 222, 104, 188, 212, 105, 190, 215, 106, 191, 213, 107, 189, 214, 108, 180, 216, 109, 182, 219, 110, 183, 217, 111, 181, 218, 112, 144, 224, 113, 146, 227, 114, 147, 225, 115, 145, 226, 116, 152, 236, 117, 154, 239, 118, 155, 237, 119, 153, 238, 120, 156, 228, 121, 158, 231, 122, 159, 229, 123, 157, 230, 124, 148, 232, 125, 150, 235, 126, 151, 233, 127, 149, 234, 256, 512, 768]
for t in range(T):
    n = int(lines[t + 1].strip())
    if n <= 255:
        print(partial[n - 1])
        continue
    index = n % 3
    lowPow4 = 4 ** (len(bin(n)[3:]) // 2)
    first = lowPow4 + (n - lowPow4) // 3
    tmp = [0, 2, 3, 1]

    def theSecond(fi):
        if fi < 128:
            j = partial.index(fi)
            return partial[j + 1]
        prev = theSecond(fi // 4)
        return prev * 4 + tmp[fi % 4]
    second = theSecond(first)
    if index == 1:
        print(first)
    elif index == 2:
        print(second)
    else:
        print(first ^ second)

Solution (Python):
from bisect import bisect, bisect_left
from collections import *
from heapq import *
from math import gcd, ceil, sqrt, floor, inf
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def A(n):
    return [0] * n

def AI(n, x):
    return [x] * n

def A2(n, m):
    return [[0] * m for i in range(n)]

def G(n):
    return [[] for i in range(n)]

def GP(it):
    return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    fact(x, mod)
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa.reverse()

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def floorsum(a, b, c, n):
    if a == 0:
        return b // c * (n + 1)
    if a >= c or b >= c:
        return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
    m = (a * n + b) // c
    return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
    return n & -n

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans

class ST:

    def __init__(self, arr):
        n = len(arr)
        mx = n.bit_length()
        self.st = [[0] * mx for i in range(n)]
        for i in range(n):
            self.st[i][0] = arr[i]
        for j in range(1, mx):
            for i in range(n - (1 << j) + 1):
                self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

    def query(self, l, r):
        if l > r:
            return -inf
        s = (r + 1 - l).bit_length() - 1
        return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

    def __init__(self, n):
        self.c = [-1] * n

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def find(self, x):
        if self.c[x] < 0:
            return x
        self.c[x] = self.find(self.c[x])
        return self.c[x]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] > self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

    def size(self, x):
        return -self.c[self.find(x)]

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

class UF:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n
        self.size = AI(n, 1)
        self.edge = A(n)

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            self.edge[pu] += 1
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            self.edge[pu] += self.edge[pv] + 1
            self.size[pu] += self.size[pv]
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv
            self.edge[pv] += self.edge[pu] + 1
            self.size[pv] += self.size[pu]

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return flag

def dij(s, graph):
    d = AI(n, inf)
    d[s] = 0
    heap = [(0, s)]
    vis = A(n)
    while heap:
        (dis, u) = heappop(heap)
        if vis[u]:
            continue
        vis[u] = 1
        for (v, w) in graph[u]:
            if d[v] > d[u] + w:
                d[v] = d[u] + w
                heappush(heap, (d[v], v))
    return d

def bell(s, g):
    dis = AI(n, inf)
    dis[s] = 0
    for i in range(n - 1):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
    change = A(n)
    for i in range(n):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                change[v] = 1
    return dis

def lcm(a, b):
    return a * b // gcd(a, b)

def lis(nums):
    res = []
    for k in nums:
        i = bisect.bisect_left(res, k)
        if i == len(res):
            res.append(k)
        else:
            res[i] = k
    return len(res)

def RP(nums):
    n = len(nums)
    s = set(nums)
    d = {}
    for (i, k) in enumerate(sorted(s), 1):
        d[k] = i
    bi = BIT([0] * (len(s) + 1))
    ans = 0
    for i in range(n - 1, -1, -1):
        ans += bi.query(d[nums[i]] - 1)
        bi.update(d[nums[i]], 1)
    return ans

def michange(a, b):
    d = defaultdict(deque)
    for (i, x) in enumerate(b):
        d[x].append(i)
    order = A(len(a))
    for (i, x) in enumerate(a):
        if not d:
            return -1
        order[i] = d[x].popleft()
    return RP(order)

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None

def nb(i, j, n, m):
    for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < n and 0 <= nj < m:
            yield (ni, nj)

def topo(n):
    q = deque()
    res = []
    for i in range(1, n + 1):
        if ind[i] == 0:
            q.append(i)
            res.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            ind[v] -= 1
            if ind[v] == 0:
                q.append(v)
                res.append(v)
    return res

@bootstrap
def gdfs(r, p):
    for ch in g[r]:
        if ch != p:
            yield gdfs(ch, r)
    yield None
''

@bootstrap
def dfs(r, p):
    par[r] = p
    for ch in g[r]:
        if ch != p:
            dep[ch] = dep[r] + 1
            yield dfs(ch, r)
    yield None
t = N()
for i in range(t):
    n = N()
    k = 1
    while k <= n:
        k *= 4
    k >>= 2
    if k == n:
        ans = n
    else:
        q = n - k
        if q % 3 == 0:
            ans = q // 3 + k
        elif q % 3 == 1:
            g = q // 3
            mul = 1
            ans = k * 2
            d = [0, 2, 3, 1]
            while g:
                (g, m) = divmod(g, 4)
                ans += d[m] * mul
                mul *= 4
        else:
            ans = k * 3
            g = q // 3
            mul = 1
            d = [0, 3, 1, 2]
            while g:
                (g, m) = divmod(g, 4)
                ans += d[m] * mul
                mul *= 4
    print(ans)
''