oj.uz

Submission #238206

# Submission time Handle Problem Language Result Execution time Memory
238206 2020-06-10T08:21:23 Z NONAME Dojave (COCI17_dojave) C++17
140 / 140
 944 ms 185848 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 115192 KB Output is correct
2 Correct 78 ms 115320 KB Output is correct
3 Correct 82 ms 115192 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 115192 KB Output is correct
2 Correct 77 ms 115316 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 115448 KB Output is correct
2 Correct 90 ms 115552 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 115576 KB Output is correct
2 Correct 73 ms 115704 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 116264 KB Output is correct
2 Correct 80 ms 115960 KB Output is correct
3 Correct 79 ms 115960 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 119292 KB Output is correct
2 Correct 92 ms 118952 KB Output is correct
3 Correct 126 ms 122388 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 119288 KB Output is correct
2 Correct 109 ms 122616 KB Output is correct
3 Correct 285 ms 130756 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 131448 KB Output is correct
2 Correct 162 ms 130004 KB Output is correct
3 Correct 230 ms 129784 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 179700 KB Output is correct
2 Correct 944 ms 185080 KB Output is correct
3 Correct 386 ms 163452 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 179832 KB Output is correct
2 Correct 556 ms 175356 KB Output is correct
3 Correct 580 ms 174488 KB Output is correct
4 Correct 766 ms 185848 KB Output is correct