QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86515#1899. Maximaze XOR sumZuqa#WA 2ms3456kbC++172.3kb2023-03-09 23:38:122023-03-09 23:38:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-09 23:38:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3456kb
  • [2023-03-09 23:38:12]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

struct gauss
{
    vector<ll> setOfXors;

    void ins(ll x)
    {    ///Add X to Gaussian Basis
        for(auto v: setOfXors)
            x = min(x, x ^ v);
        if(x)
            setOfXors.push_back(x);
    }

    vector<int> qry(ll x)
    { ///Get maximum subsequence XOR ^ x
        vector<int> ret;
        for(int i = 0; i < setOfXors.size(); i++)
        {
            ll v = setOfXors[i];
            if((x ^ v) > x)
            {
                ret.push_back(i);
                x = max(x, x ^ v);
            }
        }
        return ret;
    }
};

void doWork()
{
    int n;
    cin >> n;

    ll xrA = 0, xrB = 0;
    vector<ll> a(n), b(n);
    for(int i = 0; i < n; i++)
        cin >> a[i], xrA ^= a[i];

    for(int i = 0; i < n; i++)
        cin >> b[i], xrB ^= b[i];

    vector<int> swaps;
    ll ans = xrA + xrB;
    while(1)
    {
        gauss g;
        for(auto &it: a)
            g.ins(it);

        auto x = g.qry(0);
        for(auto &it: x)
            swap(a[it], b[it]);

        for(int i = 0; i < n; i++)
            xrA ^= a[i], xrB ^= b[i];

        if(xrA + xrB > ans)
            swaps = x;
        else
        {
            for(auto &it: x)
                swap(a[it], b[it]);
            break;
        }
        ans = max(ans, xrA + xrB);
    }
    cout << ans << ' ' << swaps.size() << '\n';
    for(auto &it: swaps)
        cout << it + 1;
}

signed main()
{
    FIO
    int T = 1;
//    cin >> T;
    for(int i = 1; i <= T; i++)
        doWork();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3456kb

input:

2
1 1
2 2

output:

6 1
1

result:

ok n=2

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3416kb

input:

3
2 1 4
4 0 4

output:

14 3
123

result:

wrong answer Integer 123 violates the range [1, 3]