QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86447#1899. Maximaze XOR sumtriplem5ds#WA 2ms3476kbC++202.2kb2023-03-09 21:48:452023-03-09 21:48:49

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 21:48:49]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3476kb
  • [2023-03-09 21:48:45]
  • 提交

answer

///Enta etfsh5t nseet el rank

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
//#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ull = unsigned long long;
using uint = uint32_t;
using ii = pair<int, int>;

const int N = 3e6 + 6, A = 26, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-9;
const ll INF = 1e15;
int val = 0;
vector<tuple<int, int, bitset<64>>> vec;

void ins(int x, int i) {
    bitset<64> bt2;
    for (auto [v, i, bt]: vec) {
        if ((v ^ x) < x) {
            bt2 ^= bt;
            x ^= v;
        }
    }

    if (x) {
        bt2[vec.size()] = 1;
        vec.push_back({x, i, bt2});
    }
}

void doWork() {

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    f(i, 0, n) {
        cin >> a[i];
        val ^= a[i];
    }
    f(i, 0, n) {
        cin >> b[i];
        val ^= b[i];
    }
    f(i, 0, n) {
        a[i] ^= (a[i] & val);
        b[i] ^= (b[i] & val);
        ins(a[i] ^ b[i], i);
    }
    int ans = 0;
    bitset<64> res;
    for (auto [v, i, bt]: vec) {
        if ((ans ^ v) > ans) {
            res ^= bt;
            ans ^= v;
        }
    }
    cout << ans * 2 + val << ' ' << res.count() << '\n';
    f(i, 0, 64) if (res[i])cout << get<1>(vec[i]) + 1 << ' ';
}


int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    int t = 1;
//    cin >> t;
    while (t--)
        doWork();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3368kb

input:

2
1 1
2 2

output:

6 1
1 

result:

ok n=2

Test #2:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

3
2 1 4
4 0 4

output:

7 0

result:

ok n=3

Test #3:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

10
12 0 4 3 1 1 12 3 11 11
3 3 14 6 14 15 1 15 5 2

output:

26 1
1 

result:

ok n=10

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3476kb

input:

50
9 27 19 1 31 10 2 7 25 26 12 25 15 18 11 15 30 25 31 2 5 30 8 18 8 17 14 2 17 7 26 26 10 25 26 5 3 5 1 17 18 12 4 17 14 19 30 30 20 2
13 18 3 8 18 11 31 20 21 14 17 29 31 2 5 28 31 17 10 13 6 10 22 18 10 2 0 15 7 14 4 15 25 10 3 30 3 21 0 12 11 19 4 16 27 10 26 3 2 5

output:

35 1
1 

result:

wrong answer Wrong sum