Submission #923946

#	Time	Username	Problem	Language	Result	Execution time	Memory
923946		daoquanglinh2007	Broken Device (JOI17_broken_device)	C++17	0 / 100	2102 ms	1384 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
 
const int MOD1 = 1e9+7, MOD2 = 1e9+9;
 
bool block[150], mark[150];
vector <int> arr;
vector <pii> v;
vector <pii>::iterator it;
 
int binpow(int k, int MOD){
	// return (2^k) % MOD;
	int x = 1;
	while (k > 0){
		x = (long long)x*(1LL<<min(k, 30))%MOD;
		k = max(k-30, 0);
	}
	return x;
}
 
int MITM(int X, int MOD){
	v.clear();
	for (int i = 0; i < (1<<15); i++){
		int tmp = 0;
		for (int j = 0; j < 15; j++){
			if ((i>>j)&1) tmp = (tmp+binpow(arr[j], MOD))%MOD;
		}
		v.push_back(mp(tmp, i));
	}
	for (int i = 0; i < (1<<15); i++){
		int tmp = 0;
		for (int j = 0; j < 15; j++){
			if ((i>>j)&1) tmp = (tmp+binpow(arr[j+15], MOD))%MOD;
		}
		tmp = (X+MOD-tmp)%MOD;
		if (tmp > v.back().fi) continue;
		int j = lower_bound(v.begin(), v.end(), mp(tmp, -1))-v.begin();
		if (v[j].fi == tmp){
			return (i<<15)+v[j].se;
		}
	}
	return -1;
}
 
void Anna(int N, long long X, int K, int P[]){
	memset(block, 0, sizeof(block));
	memset(mark, 0, sizeof (mark));
	for (int i = 0; i < K; i++) block[P[i]] = 1;
	
	arr.clear();
	for (int i = 0; i < 75; i++)
		if (!block[i] && isz(arr) < 30) arr.push_back(i);
		else mark[i] = 1;
		
	int ans1 = MITM(X%MOD1, MOD1);
	if (ans1 == -1){
		for (int t : arr) mark[t] = 1;
		arr.clear();
		for (int i = 74; i >= 0; i--)
			if (!block[i] && isz(arr) < 30){
				arr.push_back(i);
				mark[i] = 0;
			}
		ans1 = MITM(X%MOD1, MOD1);
	}
	
	for (int i = 0; i < isz(arr); i++) Set(arr[i], (ans1>>i)&1);
	
	arr.clear();
	for (int i = 75; i < 150; i++)
		if (!block[i] && isz(arr) < 30) arr.push_back(i-75);
		else mark[i] = 1;
		
	int ans2 = MITM(X%MOD2, MOD2);
	
	if (ans2 == -1){
		for (int t : arr) mark[t+75] = 1;
		arr.clear();
		for (int i = 149; i >= 75; i--)
			if (!block[i] && isz(arr) < 30){
				arr.push_back(i-75);
				mark[i] = 0;
			}
		ans2 = MITM(X%MOD2, MOD2);
	}
	
	for (int i = 0; i < isz(arr); i++) Set(arr[i]+75, (ans2>>i)&1);
	
	for (int i = 0; i < 150; i++)
		if (mark[i]) Set(i, 0);
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;

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

const int R1 = 500000004, R2 = -500000003;

int binpow2(int k, int MOD){
	// return (2^k) % MOD;
	int x = 1;
	while (k > 0){
		x = (long long)x*(1LL<<min(k, 30))%MOD;
		k = max(k-30, 0);
	}
	return x;
}

long long mul(long long x, long long y, long long MOD){
	long long res = (__int128)x*(__int128)y%MOD;
	if (res < 0) res += MOD;
	return res;
}

long long Bruno(int N, int A[]){
	long long ans1 = 0, ans2 = 0;
	for (int i = 0; i < 75; i++)
		if (A[i]) ans1 = (ans1+binpow2(i, MOD1))%MOD1;
	for (int i = 75; i < 150; i++)
		if (A[i]) ans2 = (ans2+binpow2(i-75, MOD2))%MOD2;
		
	long long MOD = (long long)MOD1*MOD2;
	ans1 = mul(mul(ans1, R2, MOD), MOD2, MOD);
	ans2 = mul(mul(ans2, R1, MOD), MOD1, MOD);
	
	return (ans1+ans2)%MOD;
}

• Subtask 1: 0 / 100