oj.uz

Submission #1078529

# Submission time Handle Problem Language Result Execution time Memory
1078529 2024-08-27T19:22:06 Z someone Broken Device (JOI17_broken_device) C++14
0 / 100
 1840 ms 6880 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using i64 = long long;
using namespace std;

//Credits for mod_int : hugopm
template<int MOD__>
struct mod_int {
	static constexpr int MOD_ = MOD__;
	int x;
	mod_int() : x(0) { }
	mod_int(long long u) {
		if (u >= MOD_ || u < 0) {
			u %= MOD_;
			if (u < 0) {
				u += MOD_;
			}
		}
		x = u;
	}
	mod_int(const mod_int &m) : x(m.x) { }
	mod_int& operator=(const mod_int &m) {
		x = m.x;
		return *this;
	}

	friend bool operator==(const mod_int& a, const mod_int& b) {
		return a.x == b.x;
	}

	friend bool operator!=(const mod_int& a, const mod_int& b) {
		return a.x != b.x;
	}

	friend bool operator<(const mod_int& a, const mod_int& b) {
		return a.x < b.x;
	}

	friend std::ostream& operator << (std::ostream& out, const mod_int& a) {
		return out << a.x;
	}

	friend std::istream& operator >> (std::istream& in, mod_int& a) {
		long long x_;
		in >> x_;
		a = mod_int(x_);
		return in;
	}

	mod_int& operator+=(const mod_int& m) {
		x += m.x;
		if (x >= MOD_) {
			x -= MOD_;
		}
		return *this;
	}

	mod_int& operator-=(const mod_int& m) {
		x -= m.x;
		if (x < 0) {
			x += MOD_;
		}
		return *this;
	}

	mod_int& operator*=(const mod_int& m) {
		x = int((long long)(x) * (long long)(m.x) % MOD_);
		return *this;
	}	

	friend mod_int operator-(const mod_int &a) {
		mod_int res(a);
		if (res.x != 0) {
			res.x = MOD_-res.x;
		}
		return res;
	}

	friend mod_int operator+(const mod_int& a, const mod_int &b) {
		return mod_int(a) += mod_int(b);
	}

	friend mod_int operator-(const mod_int& a, const mod_int &b) {
		return mod_int(a) -= mod_int(b);
	}

	friend mod_int operator*(const mod_int& a, const mod_int &b) {
		return mod_int(a) *= mod_int(b);
	}

	mod_int f2() {
		return mod_int(x) += mod_int(x);
	}

	static long long fp(long long u, long long k) {
		long long res = 1;
		while (k > 0) {
			if (k & 1) {
				res = (res * u) % MOD_;
			}
			u = (u * u) % MOD_;
			k /= 2;
		}
		return res;
	}

	mod_int fastpow(long long k) {
		return mod_int(fp(x, k));
	}
	mod_int inv() {
		return mod_int(fp(x, MOD_-2));
	}

	static mod_int sign(long long k) {
		return ((k & 1) ? mod_int(MOD_ - 1) : mod_int(1));
	}

	std::vector<mod_int> all_pow(int k) {
		std::vector<mod_int> res(k+1);
		res[0].x = 1;
		for (int i = 1; i <= k; ++i) {
			res[i].x = (1ll * res[i-1].x * x) % MOD_;
		}
		return res;
	}
};

const i64 MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;

void Anna(int N, long long X, int K, int P[]) {
    vector<bool> broken(N);
    for(int i = 0; i < K; i++)
        broken[P[i]] = 1;
    
    mt19937 rng(42);
    X ^= rng();
    vector<array<int, 2>> crt[2];
    for(int i = 0; i < N/2; i++) {
        int val = rng() % MOD1;
        if(!broken[i]) crt[0].push_back({val, i});
    }
    for(int i = N/2; i < N; i++) {
        int val = rng() % MOD2;
        if(!broken[i]) crt[1].push_back({val, i});
    }

    vector<int> ans(N);
    for(int i = 0; i < 2; i++) {
        crt[i].resize(34);
        vector<array<int, 3>> pos(1 << 18);
        int mod = (i == 0 ? MOD1 : MOD2);
        for(int j = (1 << 17); j < (1 << 18); j++)
            pos[j][0] = (mod - X % mod) % mod, pos[j][1] = 17;
        for(int j = 0; j < (1 << 18); j++)
            pos[j][2] = j & ((1 << 17) - 1);
        for(int j = 0; j < 17; j++)
            for(int mask = 0; mask < (1 << 17); mask++)
                if(mask & (1 << j))
                    pos[mask][1] = (pos[mask][1] + crt[i][j][0]) % mod;
        for(int j = 0; j < 17; j++)
            for(int mask = (1 << 17); mask < (1 << 18); mask++)
                if(mask & (1 << j))
                    pos[mask][1] = (pos[mask][1] + mod - crt[i][j][0]) % mod;
        sort(all(pos));
        for(int j = 1; j < sz(pos); j++)
            if(pos[j][1] == pos[j-1][1]) {
                for(int k = 0; k < 17; k++)
                    if(pos[j][2] & (1 << k))
                        ans[crt[i][pos[j][1] + k][1]] = 1;
                for(int k = 0; k < 17; k++)
                    if(pos[j-1][2] & (1 << k))
                        ans[crt[i][pos[j-1][1] + k][1]] = 1;
                break;
            }
    }

    for(int i = 0; i < N; i++)
        Set(i, ans[i]);
}

#include "Brunolib.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using i64 = long long;
using namespace std;

const i64 MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;

using ll = __int128;

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}

ll crt(ll a, ll m, ll b, ll n) {
	if (n > m) swap(a, b), swap(m, n);
	ll x, y, g = euclid(m, n, x, y);
	assert((a - b) % g == 0); // else no solution
	x = (b - a) % n * x % n / g * m + a;
	return x < 0 ? x + m*n/g : x;
}

long long Bruno( int N, int A[] ){
    mt19937 rng(42);
    i64 xored = rng(), a = 0, b = 0;
    for(int i = 0; i < N/2; i++) {
        i64 val = rng();
        if(A[i]) a ^= val;
    }
    for(int i = N/2; i < N; i++) {
        i64 val = rng();
        if(A[i]) b ^= val;
    }

    return ((i64)crt(a, MOD1, b, MOD2)) ^ xored;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 765 ms 6600 KB Execution killed with signal 11
2 Runtime error 233 ms 6600 KB Execution killed with signal 11
3 Runtime error 35 ms 6740 KB Execution killed with signal 11
4 Runtime error 247 ms 6592 KB Execution killed with signal 11
5 Runtime error 156 ms 6592 KB Execution killed with signal 11
6 Runtime error 1420 ms 6600 KB Execution killed with signal 11
7 Runtime error 101 ms 6716 KB Execution killed with signal 11
8 Runtime error 96 ms 6604 KB Execution killed with signal 11
9 Runtime error 45 ms 6620 KB Execution killed with signal 11
10 Runtime error 409 ms 6600 KB Execution killed with signal 11
11 Runtime error 500 ms 6608 KB Execution killed with signal 11
12 Runtime error 36 ms 6744 KB Execution killed with signal 11
13 Runtime error 277 ms 6716 KB Execution killed with signal 11
14 Runtime error 1024 ms 6880 KB Execution killed with signal 11
15 Runtime error 1840 ms 6620 KB Execution killed with signal 11
16 Runtime error 101 ms 6604 KB Execution killed with signal 11
17 Runtime error 459 ms 6592 KB Execution killed with signal 11
18 Runtime error 372 ms 6600 KB Execution killed with signal 11
19 Runtime error 216 ms 6720 KB Execution killed with signal 11
20 Runtime error 156 ms 6592 KB Execution killed with signal 11
21 Runtime error 157 ms 6604 KB Execution killed with signal 11
22 Runtime error 1143 ms 6720 KB Execution killed with signal 11
23 Runtime error 656 ms 6600 KB Execution killed with signal 11
24 Runtime error 35 ms 6628 KB Execution killed with signal 11
25 Runtime error 571 ms 6848 KB Execution killed with signal 11
26 Runtime error 99 ms 6720 KB Execution killed with signal 11
27 Runtime error 35 ms 6740 KB Execution killed with signal 11
28 Runtime error 414 ms 6596 KB Execution killed with signal 11
29 Runtime error 156 ms 6808 KB Execution killed with signal 11
30 Runtime error 35 ms 6740 KB Execution killed with signal 11
31 Runtime error 814 ms 6592 KB Execution killed with signal 11
32 Runtime error 348 ms 6716 KB Execution killed with signal 11
33 Runtime error 434 ms 6716 KB Execution killed with signal 11
34 Runtime error 327 ms 6720 KB Execution killed with signal 11
35 Runtime error 171 ms 6592 KB Execution killed with signal 11
36 Runtime error 303 ms 6600 KB Execution killed with signal 11
37 Runtime error 1553 ms 6608 KB Execution killed with signal 11
38 Runtime error 161 ms 6716 KB Execution killed with signal 11
39 Runtime error 674 ms 6712 KB Execution killed with signal 11
40 Runtime error 784 ms 6604 KB Execution killed with signal 11