Submission #238206

#	Time	Username	Problem	Language	Result	Execution time	Memory
238206		NONAME	Dojave (COCI17_dojave)	C++17	140 / 140	944 ms	185848 KiB

dojave

#include <bits/stdc++.h>
#include <random>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define el '\n'
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
using namespace std;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef unsigned long long ull;

const int N = (1 << 21);

ull vl[N], n, xr, sm, ans;
unordered_map <ull, ull> mem[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    if (n == 1) {
        cout << 2;
        return 0;
    }

    n = 1 << n;
    ull fx = n - 1;

    for (int i = 0; i < n; ++i) {
        int j = fx ^ i;

        if (j < i)
            continue;

        vl[i] = rnd();
        vl[j] = ull(0) - vl[i];
    }

    mem[0][0] = 1;

    for (int i = 0; i < n; ++i) {
        ull x;
        cin >> x;

        xr ^= x;
        sm += vl[x];

        ans += mem[xr][sm];

        mem[xr][sm]++;
    }

    cout << ull(n) * ull(n + 1) / ull(2) - ans;
}

Compilation message (stderr)

dojave.cpp: In function 'int main()':
dojave.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < n; ++i) {
                     ~~^~~
dojave.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < n; ++i) {
                     ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14