提出 #72761591

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 5e6 + 5;
bool vis[N], a[N];
vector<vector<int>> adj;
vector<int> c[2];

void dfs(int v, int col)
{
    if(vis[v])
        return;
    c[col].push_back(v);
    vis[v] = 1;
    for(int x : adj[v])
        dfs(x, 1 - col);
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt;
    cin >> tt;
    while(tt--)
    {
        ll q, l, r;
        cin >> q >> l >> r;
        if(q == 0)
        {
            for(ll i = 60; i >= 0; i--)
            {
                ll bl = ((1ll << i) & l), br = ((1ll << i) & r);
                if(bl == br)
                {
                    if(bl > 0)
                    {
                        l -= bl;
                        r -= bl;
                    }
                }
                else
                    break;
            }
            if(l == r)
            {
                cout << 1 << '\n';
                continue;
            }
            ll x = 1;
            while(2 * x <= r)
                x *= 2;
            ll ans, l1 = (x - l), l2 = (r - x + 1), len = (r - l + 1);
            if(len <= x)
            {
                ans = (l1 + 1) / 2 + (l2 + 1) / 2;
            }
            else
            {
                ans = (len + 1) / 2;
            }
            cout << ans << '\n';
        }
        else
        {
            ll len = r - l + 1;
            for(int i = 0; i < len; i++)
                a[i] = vis[i] = 0;
            adj.assign(len, {});
            for(ll x = l; x <= r; x++)
            {
                for(ll bt = 0; bt < 60; bt++)
                {
                    if(((1ll << bt) & x) == 0)
                    {
                        ll y = x + (1ll << bt);
                        if(y <= r)
                        {
                            adj[x - l].push_back(y - l);
                            adj[y - l].push_back(x - l);
                        }
                    }
                }
            }
            for(int i = 0; i < len; i++)
            {
                if(vis[i])
                    continue;
                c[0].clear();
                c[1].clear();
                dfs(i, 0);
                if(c[0].size() > c[1].size())
                    for(int x : c[0])
                        a[x] = 1;
                else    
                    for(int x : c[1])
                        a[x] = 1;
            }
            for(int i = 0; i < len; i++)
                cout << a[i] ;
            cout << '\n';
        }
    }
    return 0;
}

提出情報

ジャッジ結果