oj.uz

Submission #342618

# Submission time Handle Problem Language Result Execution time Memory
342618 2021-01-02T13:46:38 Z Olerinskiy Intergalactic ship (IZhO19_xorsum) C++14
17 / 100
 2000 ms 548 KB 
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert> 
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
#include <chrono>
#include <stack>

using namespace std;

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

istream& operator>> (istream& in, pii& b) {
    in >> b.first >> b.second;
    return in;
}

ostream& operator<< (ostream& out, const pii& b) {
    out << "{" << b.first << ", " << b.second << "}";
    return out;
}

template<typename T> ostream& operator<< (ostream& out, const vector<T>& a) {
    for (auto k : a) out << k << " ";
    return out;
}

template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}

#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << endl;
    const long long INF = 1e18;
    // const long long mod = 2600000069;
    // const long long p = 10;
#else
    #define dbg(x) 57
    const long long INF = 1e18;
    // const long long mod = 2600000069;  
    // const long long p = 179;
#endif

const ld PI = 4 * atan(1);

#define time clock() / (double) CLOCKS_PER_SEC

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,sse3,sse4")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("avx2")  
// #pragma GCC optimize("section-anchors")
// #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
// #pragma GCC optimize("vpt")
// #pragma GCC optimize("rename-registers")
// #pragma GCC optimize("move-loop-invariants")
// #pragma GCC optimize("unswitch-loops")
// #pragma GCC optimize("function-sections")
// #pragma GCC optimize("data-sections")

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1010;
const int mod = 1e9 + 7;

int n, q;
int a[N];
int l[N], r[N], x[N];
int b[N], pref[N], suf[N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> l[i] >> r[i] >> x[i];
        l[i]--, r[i]--;
    }
    int ans = 0;
    for (int i = 0; i < (1 << q); i++) {
        for (int j = 0; j < n; j++) {
            b[j] = 0;
        }
        for (int j = 0; j < q; j++) {
            if ((i >> j) & 1) {
                b[l[j]] ^= x[j];
                b[r[j] + 1] ^= x[j];
            }
        }
        int curx = 0;
        for (int i = 0; i < n; i++) {
            curx ^= b[i];
            a[i] ^= curx;
        }
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += a[j];
                ans += sum * sum % mod;
                if (ans >= mod) ans -= mod;
            }
        }
        // pref[0] = a[0];
        // for (int i = 1; i < n; i++) {
        //     pref[i] = pref[i - 1] + a[i] * (i + 1);
        //     if (pref[i] >= mod) pref[i] -= mod;
        // }
        // suf[n - 1] = a[n - 1];
        // for (int i = n - 2; i >= 0; i--) {
        //     suf[i] = suf[i + 1] + a[i] * (n - i);
        //     if (suf[i] >= mod) suf[i] -= mod;
        // }
        // for (int i = 0; i < n - 1; i++) {
        //     ans += 2ll * pref[i] * suf[i + 1] % mod;
        //     if (ans >= mod) ans -= mod;
        //     ans += a[i] * (i + 1) * (n - i) % mod;
        //     if (ans >= mod) ans -= mod;
        // }
        curx = 0;
        for (int i = 0; i < n; i++) {
            curx ^= b[i];
            a[i] ^= curx;
        }
    }
    cout << ans << "\n";
}
/*

*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 13 ms 364 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 424 KB Output is correct
2 Correct 1402 ms 492 KB Output is correct
3 Correct 1422 ms 364 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 424 KB Output is correct
2 Correct 1402 ms 492 KB Output is correct
3 Correct 1422 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 13 ms 364 KB Output is correct
9 Correct 1408 ms 424 KB Output is correct
10 Correct 1402 ms 492 KB Output is correct
11 Correct 1422 ms 364 KB Output is correct
12 Incorrect 53 ms 364 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 13 ms 364 KB Output is correct
9 Correct 1408 ms 424 KB Output is correct
10 Correct 1402 ms 492 KB Output is correct
11 Correct 1422 ms 364 KB Output is correct
12 Incorrect 1 ms 364 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 13 ms 364 KB Output is correct
9 Incorrect 104 ms 548 KB Output isn't correct
10 Halted 0 ms 0 KB -