#743493 (C++14) No.1863 Xor Sum 2...?

提出ソース
結果

問題	No.1863 Xor Sum 2...?
ユーザー	👑 AngrySadEight
提出日時	2022-03-04 22:30:53
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	18,811 bytes
コンパイル時間	2,336 ms
コンパイル使用メモリ	193,508 KB
実行使用メモリ	34,560 KB
最終ジャッジ日時	2024-07-18 21:03:33
合計ジャッジ時間	5,675 ms
ジャッジサーバーID （参考情報）	judge4 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	56 ms 16,640 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	79 ms 21,760 KB
testcase_16	WA	-
testcase_17	AC	45 ms 13,824 KB
testcase_18	WA	-
testcase_19	AC	36 ms 11,776 KB
testcase_20	AC	63 ms 18,048 KB
testcase_21	WA	-
testcase_22	AC	32 ms 10,624 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	135 ms 34,560 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	136 ms 34,432 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(), v.end()
#define mod1 1000000007
#define mod2 998244353
typedef long long ll;

vector<ll> bitconversion(ll i, ll n, ll N)
{
    //数字iをn進数にして，長さNの配列にして返す。
    //例えば，bitconversion(33,3,4)={1,0,2,0}。
    ll x = 1;
    rep(j, N)
    {
        x *= n;
    }
    vector<ll> vec(N);
    rep(j, N)
    {
        x /= n;
        vec[j] = i / x;
        i -= x * vec[j];
    }
    return vec;
}

int ctoi(char c)
{
    // char型の1桁の数をint型に変える。
    switch (c)
    {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return 0;
    }
}

vector<int> topological_sort(vector<vector<int>> &connection, vector<int> &count, int N)
{
    // vectorをトポロジカルソートして返す。
    // connectionにはそこからたどり着くことの出来る頂点の番号をあらかじめ入れておく。
    // countにはその頂点に入ってくる頂点の数を入れておく。
    vector<int> ans(0);
    queue<int> que;

    for (int i = 0; i < N; i++)
    {
        if (count[i] == 0)
        {
            que.push(i);
        }
    }

    while (que.size() != 0)
    {
        int v = que.front();
        que.pop();

        for (int i = 0; i < connection[v].size(); i++)
        {
            count[connection[v][i]] -= 1;
            if (count[connection[v][i]] == 0)
            {
                que.push(connection[v][i]);
            }
        }
        ans.push_back(v);
    }

    return ans;
}

struct union_find
{
    vector<int> par;
    vector<int> rank;
    vector<int> siz;
    vector<int> siz2;

    union_find(int N) : par(N), rank(N), siz(N), siz2(N)
    {
        rep(i, N)
        {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
            siz2[i] = 0;
        }
    }
    //宣言パート。union_findを宣言する時は，例えばunion_find tree(N)のようにする。

    int root(int x)
    {
        if (par[x] == x)
        {
            return x;
        }
        return par[x] = root(par[x]);
    }
    //頂点に対して，その根となる頂点の番号を返す。

    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry)
        {
            siz2[rx]++;
            return;
        }
        if (siz[rx] < siz[ry])
        {
            par[rx] = ry;
            siz[ry] += siz[rx];
            siz2[ry] += siz2[rx];
            siz2[ry]++;
        }
        else
        {
            par[ry] = rx;
            siz[rx] += siz[ry];
            siz2[rx] += siz2[ry];
            siz2[rx]++;
            if (rank[rx] == rank[ry])
                rank[rx]++;
        }
    }
    //頂点xとyをくっつけてやる。計算量削減のため，それぞれの木の「高さ」(rank)をカウントしておいて，
    //その高さの高い方に低い方をくっつけてやるようにする。

    bool same(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    //頂点xとyが同じ木に属するかを判定する。

    int size(int x)
    {
        return siz[root(x)];
    }
    //頂点xが含まれる木のサイズ。

    int size2(int x)
    {
        return siz2[root(x)];
    }
};

ll gcd(ll a, ll b)
{
    // aとbの最大公約数。
    ll r, temp;
    if (a < b)
    {
        temp = a;
        a = b;
        b = temp;
    }
    while ((r = a % b) != 0)
    {
        a = b;
        b = r;
    }
    return b;
}

ll iterative_square_method(ll i, vector<ll> &vec, ll N, ll mod)
{
    //繰り返し二乗法。iのX乗をmodで割った余りを求める。
    //なお，Xは，事前にmoddividing関数で長さNの二進数vector(vec)に直しておく必要がある。
    //例えば，2の100000乗をmod1e9+7で求めたいときは，
    // iterative_square_method(2,moddividing(100000,2,30),30,1000000007)のように書けば良い。
    ll ans = 1;
    rep(j, N)
    {
        if (vec[N - 1 - j] == 1)
            ans = (ans * i) % mod;
        i = (i * i) % mod;
    }
    return ans;
}

double iterative_square_method2(double X, vector<ll> &vec, ll N)
{
    double ans = 1;
    rep(j, N)
    {
        if (vec[N - 1 - j] == 1)
            ans = ans * X;
        X = X * X;
    }
    return ans;
}

ll moddividing(ll x, ll y)
{
    // x÷yをmod1e9+7で求める。
    vector<ll> vec(30);
    rep(i, 30)
    {
        vec[i] = y;
        y = y * y % 1000000007;
    }
    ll c = x;
    c = c * vec[0] % 1000000007;
    c = c * vec[2] % 1000000007;
    c = c * vec[9] % 1000000007;
    c = c * vec[11] % 1000000007;
    c = c * vec[14] % 1000000007;
    c = c * vec[15] % 1000000007;
    c = c * vec[17] % 1000000007;
    c = c * vec[19] % 1000000007;
    c = c * vec[20] % 1000000007;
    c = c * vec[23] % 1000000007;
    c = c * vec[24] % 1000000007;
    c = c * vec[25] % 1000000007;
    c = c * vec[27] % 1000000007;
    c = c * vec[28] % 1000000007;
    c = c * vec[29] % 1000000007;
    return c;
}

ll moddividing2(ll x, ll y)
{
    // x÷yをmod998244353で求める。
    vector<ll> vec(30);
    rep(i, 30)
    {
        vec[i] = y;
        y = y * y % 998244353;
    }
    ll c = x;
    c = c * vec[0] % 998244353;
    c = c * vec[1] % 998244353;
    c = c * vec[2] % 998244353;
    c = c * vec[3] % 998244353;
    c = c * vec[4] % 998244353;
    c = c * vec[5] % 998244353;
    c = c * vec[6] % 998244353;
    c = c * vec[7] % 998244353;
    c = c * vec[8] % 998244353;
    c = c * vec[9] % 998244353;
    c = c * vec[10] % 998244353;
    c = c * vec[11] % 998244353;
    c = c * vec[12] % 998244353;
    c = c * vec[13] % 998244353;
    c = c * vec[14] % 998244353;
    c = c * vec[15] % 998244353;
    c = c * vec[16] % 998244353;
    c = c * vec[17] % 998244353;
    c = c * vec[18] % 998244353;
    c = c * vec[19] % 998244353;
    c = c * vec[20] % 998244353;
    c = c * vec[21] % 998244353;
    c = c * vec[22] % 998244353;
    c = c * vec[24] % 998244353;
    c = c * vec[25] % 998244353;
    c = c * vec[27] % 998244353;
    c = c * vec[28] % 998244353;
    c = c * vec[29] % 998244353;
    return c;
}

struct segtree
{
    //セグメントツリー。いろんな機能があるよ。やったね。
    vector<ll> vec;

    segtree(ll N) : vec(N)
    {
        rep(i, N)
        {
            vec[i] = 0;
        }
    }
    //初期化。セグメントツリーの正体はvectorである。
    //バグが発生する可能性があるため，サイズNは（用意したいセグ木の長さ）*2よりも大きい2の累乗数で宣言してやる。

    void make(ll k, ll a, ll N)
    { // 0_indexed
        k += (N / 2);
        vec[k] = a;
    }
    //セグメントツリーのk番目の要素をaに変える。

    void sum_update(ll k, ll a, ll N)
    { // 0_indexed
        k += (N / 2);
        vec[k] = a;
        while (k > 1)
        {
            k = k / 2;
            vec[k] = vec[k * 2] + vec[k * 2 + 1];
        }
    }
    //セグメントツリー上で和の計算を行う上での前処理。k番目の要素をaに変更して，なおかつ和の計算の前処理を行う。

    void max_update(ll k, ll a, ll N)
    { // 0_indexed
        k += (N / 2);
        vec[k] = a;
        while (k > 1)
        {
            k = k / 2;
            vec[k] = max(vec[k * 2], vec[k * 2 + 1]);
        }
    }
    //セグメントツリー上で最大値を求める上での前処理。k番目の要素をaに変更して，なおかつ最大値を求める前処理を行う。

    void min_update(ll k, ll a, ll N)
    { // 0_indexed
        k += (N / 2);
        vec[k] = a;
        while (k > 1)
        {
            k = k / 2;
            vec[k] = min(vec[k * 2], vec[k * 2 + 1]);
        }
    }
    //セグメントツリー上で最小値を求める上での前処理。k番目の要素をaに変更して，なおかつ最小値を求める前処理を行う。

    ll min_query(ll a, ll b, ll k, ll l, ll r)
    { // min_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
        if (r <= a || b <= l)
            return 10000000000000000;
        if (a <= l && r <= b)
            return vec[k];
        ll vl = min_query(a, b, k * 2, l, (l + r) / 2);
        ll vr = min_query(a, b, k * 2 + 1, (l + r) / 2, r);
        return min(vl, vr);
    }
    //セグメントツリー上で最小値を求める。半開区間[a,b)(a,bは0_indexed)における最小値を求めてやる。
    // k,l,rは固定で，k=1,l=0,r=N/2として良い。

    ll check(ll i, ll N)
    {
        return vec[i + N / 2];
    }
    // i番目の要素を確認する。

    ll max_query(ll a, ll b, ll k, ll l, ll r)
    { // max_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
        if (r <= a || b <= l)
            return -100000000000000000;
        if (a <= l && r <= b)
            return vec[k];
        ll vl = max_query(a, b, k * 2, l, (l + r) / 2);
        ll vr = max_query(a, b, k * 2 + 1, (l + r) / 2, r);
        return max(vl, vr);
    }
    //セグメントツリー上で最大値を求める。半開区間[a,b)(a,bは0_indexed)における最大値を求めてやる。
    // k,l,rは固定で，k=1,l=0,r=N/2として良い。

    ll sum_query(ll a, ll b, ll k, ll l, ll r)
    { // sum_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
        if (r <= a || b <= l)
            return 0;
        if (a <= l && r <= b)
            return vec[k];
        ll vl = sum_query(a, b, k * 2, l, (l + r) / 2);
        ll vr = sum_query(a, b, k * 2 + 1, (l + r) / 2, r);
        return vl + vr;
    }
    //セグメントツリー上で和を求める。半開区間[a,b)(a,bは0_indexed)における和を求めてやる。
    // k,l,rは固定で，k=1,l=0,r=N/2として良い。
};

char itoc(int c)
{
    // int型の0から25までの値cを，(c+1)番目のchar型アルファベット1文字に変更してやる。
    switch (c)
    {
    case 0:
        return 'a';
    case 1:
        return 'b';
    case 2:
        return 'c';
    case 3:
        return 'd';
    case 4:
        return 'e';
    case 5:
        return 'f';
    case 6:
        return 'g';
    case 7:
        return 'h';
    case 8:
        return 'i';
    case 9:
        return 'j';
    case 10:
        return 'k';
    case 11:
        return 'l';
    case 12:
        return 'm';
    case 13:
        return 'n';
    case 14:
        return 'o';
    case 15:
        return 'p';
    case 16:
        return 'q';
    case 17:
        return 'r';
    case 18:
        return 's';
    case 19:
        return 't';
    case 20:
        return 'u';
    case 21:
        return 'v';
    case 22:
        return 'w';
    case 23:
        return 'x';
    case 24:
        return 'y';
    case 25:
        return 'z';
    default:
        return 'a';
    }
}

ll kruskal(vector<pair<ll, pair<int, int>>> &connect, union_find tree)
{
    //クラスカル法で，1辺を結ぶ2頂点の番号とその辺の長さが与えられた場合に
    //最小全域木を作る場合の辺の長さの総和を求める。
    // connect関数には，「1辺の長さ」「2頂点の番号」をあらかじめ入れておく。
    ll ans = 0;
    for (ll i = 0; i < connect.size(); i++)
    {
        if (!tree.same(connect[i].second.first, connect[i].second.second))
        {
            ans += connect[i].first;
            tree.unite(connect[i].second.first, connect[i].second.second);
        }
    }
    return ans;
}

void dijkstra(vector<vector<pair<ll, ll>>> &G, ll s, vector<ll> &dis)
{
    //ダイクストラ法。sを始点としたときの，最短距離を求める。
    //ここでは，Gに「第一要素＝行き先，第二要素＝コスト」として，無効グラフを考える。
    // Nには構成されるグラフの頂点の数が入る。
    //計算量は，辺の数をE，頂点の数をVとして，O(ElogV）である。
    // priority_queueの要素は「第一要素＝距離，第二要素＝頂点の番号」だから注意！
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pque;
    dis[s] = 0;
    pque.push(pair<ll, ll>(dis[s], s));
    while (!pque.empty())
    {
        pair<ll, ll> p = pque.top();
        pque.pop();
        ll v = p.second;
        if (dis[v] < p.first)
            continue;
        for (int i = 0; i < G[v].size(); i++)
        {
            if (dis[G[v][i].first] > dis[v] + G[v][i].second)
            {
                dis[G[v][i].first] = dis[v] + G[v][i].second;
                pque.push(pair<ll, ll>(dis[G[v][i].first], G[v][i].first));
            }
        }
    }
}

vector<vector<ll>> matrix_exponentiation(vector<vector<ll>> &M, vector<ll> &bin, ll N, ll K, ll mod)
{
    //行列累乗。N*N行列MのX乗を求める。ただし，Xは，事前にbitconversion関数で2進数に変えておき，その配列binを渡す必要あり。
    // NにはMの行列のサイズを，Kにはbin配列のサイズを渡す。また，modを取る場合は変数modにその値を渡す。
    vector<vector<ll>> matrix(N, vector<ll>(N));
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j < N; j++)
        {
            matrix[i][j] = M[i][j];
        }
    }
    vector<vector<ll>> ans_old_matrix(N, vector<ll>(N));
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j < N; j++)
        {
            if (i == j)
                ans_old_matrix[i][j] = 1;
            else
                ans_old_matrix[i][j] = 0;
        }
    }

    vector<vector<ll>> ans_new_matrix(N, vector<ll>(N));
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j < N; j++)
        {
            ans_new_matrix[i][j] = 0;
        }
    }

    vector<vector<ll>> new_matrix(N, vector<ll>(N));
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j < N; j++)
        {
            new_matrix[i][j] = 0;
        }
    }

    for (ll x = 0; x < K; x++)
    {
        if (bin[K - 1 - x] == 1)
        {
            for (ll i = 0; i < N; i++)
            {
                for (ll j = 0; j < N; j++)
                {
                    for (ll k = 0; k < N; k++)
                    {
                        ans_new_matrix[i][j] = (ans_new_matrix[i][j] + (ans_old_matrix[i][k] * matrix[k][j])) % mod;
                    }
                }
            }
            for (ll i = 0; i < N; i++)
            {
                for (ll j = 0; j < N; j++)
                {
                    ans_old_matrix[i][j] = ans_new_matrix[i][j];
                    ans_new_matrix[i][j] = 0;
                }
            }
        }
        for (ll i = 0; i < N; i++)
        {
            for (ll j = 0; j < N; j++)
            {
                for (ll k = 0; k < N; k++)
                {
                    new_matrix[i][j] = (new_matrix[i][j] + (matrix[i][k] * matrix[k][j])) % mod;
                }
            }
        }
        for (ll i = 0; i < N; i++)
        {
            for (ll j = 0; j < N; j++)
            {
                matrix[i][j] = new_matrix[i][j];
                new_matrix[i][j] = 0;
            }
        }
    }

    return ans_old_matrix;
}

void bellman_ford(vector<ll> &from, vector<ll> &to, vector<ll> &cost, vector<ll> &dis, ll v, ll N, ll M, bool &negative)
{
    //ベルマンフォード法。
    //頂点fromから頂点toまでの長さcostの辺が，M本張られている。頂点数はN。
    //このもとで，始点vからの最短距離disを求めることにする。
    //負の閉路がある場合はnegativeがtrueになる。
    vector<bool> hasroute(N, false);
    hasroute[v] = true;
    vector<bool> nega(N, false);
    for (ll i = 0; i < N; i++)
    {
        bool update = false;
        for (ll j = 0; j < M; j++)
        {
            if (dis[to[j]] > dis[from[j]] + cost[j])
            {
                dis[to[j]] = dis[from[j]] + cost[j];
                if (hasroute[from[j]])
                    hasroute[to[j]] = true;
                update = true;
                if (i == N - 1)
                {
                    nega[to[j]] = true;
                }
            }
        }
        if (!update)
        {
            break;
        }
    }

    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j < M; j++)
        {
            if (hasroute[from[j]] && nega[from[j]])
                nega[to[j]] = true;
        }
    }
    if (hasroute[N - 1] && nega[N - 1])
        negative = true;
}

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    vector<ll> B(N);
    rep(i,N) cin >> B[i];

    vector<ll> B_xor(N + 1);
    B_xor[0] = 0;
    rep(i,N){
        B_xor[i + 1] = B_xor[i] ^ B[i];
    }

    vector<ll> B_sum1(N + 1, 0);
    vector<ll> B_sum0(N + 1, 0);
    rep(i,N){
        if (B_xor[i + 1] == 1){
            B_sum1[i + 1] = B_sum1[i] + 1;
            B_sum0[i + 1] = B_sum0[i];
        }
        else{
            B_sum1[i + 1] = B_sum1[i];
            B_sum0[i + 1] = B_sum0[i] + 1;
        }
    }
    ll ans = 0;
    vector<vector<ll>> vec(N + 1, vector<ll>(30));
    rep(i,N + 1){
        rep(j,30){
            vec[i][j] = 0;
        }
    }
    rep(i,N){
        rep(j, 30){
            if ((A[i] >> j) & 1){
                vec[i + 1][j] = vec[i][j] + 1;
            }
            else{
                vec[i + 1][j] = vec[i][j];
            }
        }
    }

    for (ll i = 0; i < N; i++){
        if (B[i] == 0) ans++;
    }

    for (ll i = 0; i <= N - 2; i++){
        ll left = i;
        ll right = N;
        while(true){
            if (right - left <= 1){
                break;
            }
            else{
                ll center = (left + right) / 2;
                bool judge = true;
                for (ll j = 0; j < 30; j++){
                    if (vec[center + 1][j] > vec[i][j] + 1) judge = false;
                }
                if (!judge){
                    right = center;
                }
                else{
                    left = center;
                }
            }
        }
        if (left == i){
            ans += 0;
        }
        else{
            if (B_xor[i + 1] == 1){
                ans += (left - i - (B_sum0[left + 1] - B_sum0[i + 1]));
            }
            else{
                ans += (left - i - (B_sum1[left + 1] - B_sum1[i + 1]));
            }
        }
    }
    cout << ans << endl;
}
yukicoder

結果

テストケース

ソースコード
