| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 923930 | daoquanglinh2007 | Broken Device (JOI17_broken_device) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<<16); i++){
int tmp = 0;
for (int j = 0; j < 16; 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+16], 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;
}
}
}
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) < 31) arr.push_back(i);
else mark[i] = 1;
int 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) < 31) arr.push_back(i-75);
else mark[i] = 1;
int 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);
}