Submission #1078529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078529		someone	Broken Device (JOI17_broken_device)	C++14	0 / 100	1840 ms	6880 KiB

Anna

#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]);
}

Bruno

#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 / 100