562768A - The Lucky Seven Quest
Author: Bishoy Ezzat (Loyalixa Founder)
import java.util.*;
public class Main{
public static void main(String... args){
Scanner in = new Scanner(System.in);
int num = in.nextInt();
if(num % 7 == 0) System.out.print(num);
else System.out.print(num/7*7+7);
}
}
Author: Bnahmad23
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
const int N = 2e5+5, MOD = 1000000007;
int n,m,k,w,r,c;
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
cin.tie(0);
ios_base::sync_with_stdio(0);
int T;
cin>>T;
while(T--){
cin>>n>>m>>r>>c;
cin>>k>>w;
// -m <= c <= m (0 is middle)
int lo = 1,hi = k;
for(int i = 0;i<w;i++){
int a,b,cur;
cin>>a>>b>>cur;
if(a < r){
lo = max(lo,cur);
}else if(a > r){
hi = min(hi,cur);
}else {
if(c >= 0 && b >= 0){
if(b > c)
hi = min(hi,cur);
else
lo = max(lo,cur);
}else if(c <= 0 && b <= 0){
if(b > c)
lo = max(lo,cur);
else
hi = min(hi,cur);
}
}
}
cout<<lo<<" "<<hi<<endl;
}
return 0;
}
Author: Bnahmad23
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
cerr << ' ' << H;
dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
typedef long long ll;
const int N = 1e6 + 5;
int ans[N];
int x[N], k[N];
int a[N];
vector<int> pos[N];
vector<int> qu[N];
int n, q;
void test_case() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
pos[a[i]].pb(i);
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> x[i] >> k[i];
qu[x[i]].pb(i);
ans[i] = -1;
}
vector<int> tmp;
for (int i = 1; i <= 1e6; i++) {
int r = 0;
sort(all(qu[i]));
int idx = 0;
tmp.clear();
for (int j = i; j <= 1e6; j += i) {
for (auto &u : pos[j]) {
tmp.push_back(u);
}
}
sort(all(tmp));
for (auto &id : qu[i]) {
if (k[id] <= tmp.size()) {
ans[id] = tmp[k[id] - 1] + 1;
}
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
test_case();
}
return 0;
}
562768C2 - Where am I? (Harder version)
Idea: Hassan_Fathi
Prepared: Bnahmad23
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
const int N = 1e6+5, MOD = 1000000007;
int a[N];
struct SQ{
vector <int> idx;
vector <vector<int> > b;
int n,bSize,blocks;
SQ(){bSize = blocks = n = 0,idx.clear(),b.clear();}
void add(int x){
idx.push_back(x);
}
void build(){
sort(idx.begin(),idx.end());
idx.erase(unique(idx.begin(),idx.end()),idx.end());
n = idx.size();
if(n == 0)
return;
bSize = sqrt(n);
blocks = (n+bSize-1)/bSize;
b.resize((n+bSize-1)/bSize);
for(int i = 0;i<n;i++){
b[i/bSize].push_back(a[idx[i]]);
}
for(int i = 0;i<blocks;i++){
sort(b[i].begin(),b[i].end());
}
}
int walk(int s,int l,int r,int k){
for(int i = s;i<n;i++){
if(a[idx[i]] > r || a[idx[i]] < l)
continue;
k--;
if(k == 0)
return idx[i];
}
return -1;
}
int get(int l,int r,int s,int e,int k){
if(n == 0 || e < s)
return -1;
int stB = s/bSize;
int enB = e/bSize;
if(stB == enB){
for(int i = s;i<=e;i++){
if(a[idx[i]] > r || a[idx[i]] < l)
continue;
k--;
if(k == 0)
return idx[i];
}
return -1;
}
int cnt = 0;
for(int i = s;i<(stB+1)*bSize;i++){
if(a[idx[i]] > r || a[idx[i]] < l)
continue;
cnt++;
}
if(cnt >= k)
return walk(s,l,r,k);
k -= cnt;
for(int i = (stB+1);i<enB;i++){
cnt = upper_bound(b[i].begin(),b[i].end(),r) - lower_bound(b[i].begin(),b[i].end(),l);
if(cnt >= k)
return walk(i*bSize,l,r,k);
k -= cnt;
}
cnt = 0;
for(int i = enB*bSize;i<=e;i++){
if(a[idx[i]] > r || a[idx[i]] < l)
continue;
cnt++;
}
if(cnt >= k)
return walk(enB*bSize,l,r,k);
return -1;
}
};
vector <SQ> res;
int n,q;
vector <vector<int> > f;
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n;
f.resize(N);
res.resize(N);
for(int i = 1;i<=n;i++){
cin>>a[i];
f[a[i]].push_back(i);
}
for(int i = 1;i<N;i++){
for(int j = i;j<N;j+=i){
for(auto it:f[j]){
res[i].add(it);
}
}
res[i].build();
}
cin>>q;
while(q--){
int x,k,l,r,s,e;
cin>>x>>k>>l>>r>>s>>e;
vector <int> &tmp = res[x].idx;
s = lower_bound(tmp.begin(),tmp.end(),s) - tmp.begin();
e = upper_bound(tmp.begin(),tmp.end(),e) - tmp.begin() - 1;
cout<<res[x].get(l,r,s,e,k)<<endl;
}
return 0;
}
562768D - Loyalixa's Challenge
Author: Bishoy Ezzat
import java.io.*;
public class Main {
public static final int MOD = 1000_000_007;
public static final long[] powers = new long[1000_001];
public static void main(String[] args) throws IOException {
fac(1000000, MOD - 1);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
int n = Integer.parseInt(br.readLine());
sb.append((calc(9, n) - calc(5, n) - calc(4, n) + 2 * MOD) % MOD).append("\n");
}
System.out.print(sb);
}
public static long calc(int c, int n) {
return (long) c * fp(c - 1, powers[n] - 1, MOD) % MOD;
}
public static void fac(int n, int mod) {
powers[0] = 1;
for (int i = 1; i <= n; i++) {
powers[i] = powers[i - 1] * i % mod;
}
}
public static long fp(long n, long p, int mod) {
if (p == 0) return 1;
if (p == 1) return n;
long term = fp(n, p / 2, mod) % mod;
if (p % 2 == 0) return mul(term, term, mod);
else return (n % mod * mul(term, term, mod)) % mod;
}
public static long mul(long a, long b, int mod) {
return a * b % mod;
}
}
Author: Hassan_Fathi
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p , sz, rnk;
stack<tuple<int,int,int,int>> history;
int cmp;
DSU(int n){
p.resize(n);
sz.resize(n);
rnk.resize(n);
cmp = n;
for(int i = 0; i < n; i ++){
p[i] = i;
sz[i] = 1;
}
}
int find(int a){
return p[a] == a ? a : find(p[a]);
}
bool merge(int a , int b){
a = find(a);
b = find(b);
if(a == b)
return 0;
if(rnk[a] < rnk[b])
swap(a , b);
history.push({a, sz[a], rnk[a] , b});
cmp --;
p[b] = a;
if(rnk[a] == rnk[b])
rnk[a] ++;
return 1;
}
void roll_back(){
assert(history.size() > 0);
auto &[a , sza, rnka , b] = history.top();
history.pop();
sz[a] = sza;
rnk[a] = rnka;
p[b] = b;
cmp ++;
}
};
void hassan(){
int n , m;
cin >> n >> m;
DSU d(n);
for(int i = 0; i < m; i ++){
int a , b;
cin >> a >> b;
a -- , b --;
d.merge(a , b);
}
int q;
cin >> q;
while(q --){
int sz;
cin >> sz;
int cnt = 0;
bool cycle = 0;
while(sz --){
int a , b;
cin >> a >> b;
if(cycle)
continue;
a -- , b --;
if(d.merge(a , b))
cnt ++;
else
cycle = 1;
}
cout << (cycle ? "Cycle\n" : "Nop\n");
while(cnt --)
d.roll_back();
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t; while(t --)
hassan();
}
Author: Bnahmad23
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
const int N = 1e5+5,LOG = 21, MOD = 1000000007;
int n,q,a[N],ans[N];
struct Node{
int basis[LOG],sz,lazy;
bool hasLazy;
Node(){
lazy = -1;
sz = 0;
hasLazy = false;
fill(basis,basis+LOG,0);
}
Node(int x){
lazy = -1;
sz = 0;
hasLazy = false;
fill(basis,basis+LOG,0);
for(int i = LOG-1;i>=0;i--){
if(x & (1<<i)){
basis[i] = x;
break;
}
}
}
void insert(int mask){
for(int i = LOG-1;i>=0;i--){
if(mask & (1<<i)){
if(basis[i] == 0){
basis[i] = mask;
sz++;
break;
}
mask ^= basis[i];
}
}
}
Node(const Node <,const Node &rt){
lazy = -1;
sz = 0;
hasLazy = false;
fill(basis,basis+LOG,0);
for(int i = 0;i<LOG;i++){
if(lt.basis[i])
insert(lt.basis[i]);
if(rt.basis[i])
insert(rt.basis[i]);
}
}
void apply(){
vector <int> tmp;
for(int i = 0;i<LOG;i++){
if(basis[i])
tmp.push_back(basis[i] & lazy);
}
fill(basis,basis+LOG,0);
sz = 0;
for(auto it:tmp){
insert(it);
}
hasLazy = false;
lazy = -1;
}
};
vector <Node> seg;
void prop(int node,int l,int r){
if(seg[node].hasLazy){
if(l != r){
seg[node*2].hasLazy = seg[node*2+1].hasLazy = true;
seg[node*2].lazy &= seg[node].lazy;
seg[node*2+1].lazy &= seg[node].lazy;
}
seg[node].apply();
}
}
void build(int node = 1,int l = 1,int r = n){
if(l == r){
seg[node] = Node(a[l]);
return;
}
int md = (l+r)/2;
build(node*2,l,md);
build(node*2+1,md+1,r);
seg[node] = Node(seg[node*2],seg[node*2+1]);
}
void updateAND(int s,int e,int val,int node = 1,int l = 1,int r = n){
prop(node,l,r);
if(l > e || r < s)
return;
if(l >= s && r <= e){
seg[node].hasLazy = true;
seg[node].lazy &= val;
prop(node,l,r);
return;
}
int md = (l+r)/2;
updateAND(s,e,val,node*2,l,md);
updateAND(s,e,val,node*2+1,md+1,r);
seg[node] = Node(seg[node*2],seg[node*2+1]);
}
void updateIDX(int idx,int val,int node = 1,int l = 1,int r = n){
prop(node,l,r);
if(l > idx || r < idx)
return;
if(l == r){
seg[node] = Node(val);
return;
}
int md = (l+r)/2;
updateIDX(idx,val,node*2,l,md);
updateIDX(idx,val,node*2+1,md+1,r);
seg[node] = Node(seg[node*2],seg[node*2+1]);
}
Node get(int s,int e,int node = 1,int l = 1,int r = n){
prop(node,l,r);
if(l > e || r < s)
return Node();
if(l >= s && r <= e){
return seg[node];
}
int md = (l+r)/2;
return Node(get(s,e,node*2,l,md),get(s,e,node*2+1,md+1,r));
}
bool check(const Node &cur,int mask){
for(int i = LOG-1;i>=0;i--){
if(((mask >> i) & 1) == 1){
if(cur.basis[i] == 0)
return false;
mask ^= cur.basis[i];
}
}
return true;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
cin.tie(0);
ios_base::sync_with_stdio(0);
ans[0] = 1;
for(int i = 1;i<N;i++){
ans[i] = 2LL*ans[i-1] % MOD;
}
int T;
cin>>T;
while(T--){
cin>>n;
for(int i = 1;i<=n;i++){
cin>>a[i];
}
seg.assign(n*4+1,Node());
build();
cin>>q;
while(q--){
int type;
cin>>type;
if(type == 1){
int l,r,x;
cin>>l>>r>>x;
updateAND(l,r,x);
}else if(type == 2){
int l,x;
cin>>l>>x;
updateIDX(l,x);
}else {
int l,r,x;
cin>>l>>r>>x;
Node cur = get(l,r);
if(check(cur,x)){
assert(r-l+1 >= cur.sz);
cout<<ans[r-l+1-cur.sz]<<endl;
}else{
cout<<"0\n";
}
}
}
}
return 0;
}
562768G1 - Hassan Loves Primes (easy version)
Idea: Hassan_Fathi
Prepared: CaMOUFlage
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
const ll oo = 5e5+9;
ll n,a[oo];
void solve()
{
cin>>n;
cout<<n/2<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
ll tt=1;
cin>>tt;
while(tt--)
solve();
return 0;
}
562768G2 - Hassan Loves Primes (hard version)
Idea: Hassan_Fathi
Prepared: CaMOUFlage
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
const ll oo = 5e5+9;
ll n,a[oo];
void solve()
{
cin>>n;
if(n==2)
return void(cout<<"1\n");
if(n%2==0)
return void(cout<<"2\n");
bool dv=0;
for(ll i=2; i*i<=n; i++)
if(n%i==0)
{
dv=1;
break;
}
if(!dv)
return void(cout<<"1\n");
dv=0;
for(ll i=2; i*i<=n-2; i++)
if((n-2)%i==0)
{
dv=1;
break;
}
if(!dv)
cout<<"2\n";
else
cout<<"3\n";
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
ll tt=1;
cin>>tt;
while(tt--)
solve();
return 0;
}
Author: CaMOUFlage
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int M = 78499 + 5;
vector<int> sf(N) , primes , id(N);
vector<vector<pair<int,int>>> factors(N);
void PRE(){
for(int i = 1; i < N; i ++)
sf[i] = i;
for(int i = 2; i * i < N; i ++){
if(sf[i] == i){
for(int j = i * i; j < N; j += i){
if(sf[j] == j)
sf[j] = i;
}
}
}
for(int i = 2; i < N; i ++){
if(sf[i] == i)
primes.push_back(i);
}
M = primes.size();
for(int i = 0; i < M; i ++)
id[primes[i]] = i;
for(int i = 1; i < N; i ++){
int x = i;
while(sf[x] != 1){
int cnt = 0;
int p = sf[x];
while(sf[x] == p){
cnt ++;
x /= p;
}
factors[i].push_back({id[p] , cnt});
}
}
}
template <typename T>
struct fenwick {
vector<T> bit;
int n;
fenwick(int _n) {
n = _n;
bit.resize(n);
}
T pre(int i) {
T ret = 0;
for (; i >= 0; i = (i & (i + 1)) - 1)
ret += bit[i];
return ret;
}
T get(int l, int r) {
if(l > r)
return 0;
return pre(r) - pre(l - 1);
}
void update(int i, T x) {
for (; i < n; i = i | (i + 1))
bit[i] += x;
}
};
fenwick<int> fenA(M) , fenB(M);
vector<int> fA(M) , fB(M);
void hassan(){
int n;
cin >> n;
vector<int> a(n);
for(auto &x : a)
cin >> x;
auto add = [&](int x , auto &f, auto &fen , int parity){
for(auto &[p , cnt] : factors[x]){
f[p] += parity * cnt;
if((f[p] > 0) != fen.get(p , p))
fen.update(p , f[p] ? 1 : -1);
}
};
auto get_ans = [&](auto &fen){
int l = 0, r = M - 1;
while(l <= r){
int md = (l + r) / 2;
if(fen.get(0 , md) == md + 1)
l = md + 1;
else
r = md - 1;
}
r ++;
return primes[r];
};
int res = 1e9 , PA , PB;
auto update_ans = [&]{
PA = get_ans(fenA);
PB = get_ans(fenB);
res = min(res , abs(PA - PB));
};
add(a[0], fA, fenA , 1);
for(int i = 1; i < n; i ++)
add(a[i] , fB, fenB , 1);
int r = 0;
update_ans();
for(int l = 0; l < n && r < n; l ++){
while(r + 1 < n && PA - PB < 0){
update_ans();
r ++;
add(a[r] , fA, fenA , 1);
add(a[r] , fB, fenB , -1);
PA = get_ans(fenA);
PB = get_ans(fenB);
}
update_ans();
add(a[l] , fA, fenA , -1);
add(a[l] , fB, fenB , 1);
update_ans();
}
cout << res << '\n';
vector<int> to_erase;
for(auto &x : a){
for(auto &[p , cnt] : factors[x]){
to_erase.push_back(p);
}
}
sort(to_erase.begin() , to_erase.end());
to_erase.erase(unique(to_erase.begin() , to_erase.end()) , to_erase.end());
for(auto &p : to_erase){
fA[p] = fB[p] = 0;
fenA.update(p , -fenA.get(p , p));
fenB.update(p , -fenB.get(p , p));
}
}
int main(){
PRE();
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t; while(t --)
hassan();
}
Author: CaMOUFlage
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mid ((l+r)>>1)
#define ii (d<<1)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
const ll oo = 2e5+9;
ll n,a[oo],to[oo],in[oo],sz,u[oo],b[oo],out[oo],t;
ll mx[4*oo],lz[4*oo],ans[oo];
bool vis[oo],not_root[oo];
vector<vector<ll>>v;
void reset()
{
v.clear();
for(ll i=1; i<=n; i++)
vis[i] = not_root[i]=0;
for(ll i=1; i<=4*n; i++)
mx[i]=lz[i]=0;
for(ll i=1; i<=n; i++)
{
in[i]=out[i]=b[i]=0;
ans[i]=u[i]=0;
}
sz=t=0;
}
void push(ll d,ll l,ll r)
{
mx[d] += lz[d];
if(l<r)
{
lz[ii] += lz[d];
lz[ii+1] += lz[d];
}
lz[d]=0;
}
void up(ll d,ll l,ll r,ll lx,ll rx,ll val)
{
push(d,l,r);
if(rx<l||lx>r)
return;
if(lx<=l&&rx>=r)
{
lz[d] += val;
push(d,l,r);
return;
}
up(ii,l,mid,lx,rx,val);
up(ii+1,mid+1,r,lx,rx,val);
mx[d] = max(mx[ii], mx[ii+1]);
}
void dfs0(ll d)
{
in[d] = ++t;
for(auto&z:v[d])
dfs0(z);
out[d]=t;
up(1,1,sz,in[d],out[d],b[d]);
}
void dfs1(ll d,ll sum)
{
sum += b[d];
up(1,1,sz,in[d],out[d],-b[d]);
ans[d] = sum + mx[1];
for(auto&z:v[d])
dfs1(z,sum);
up(1,1,sz,in[d],out[d],b[d]);
}
void solve()
{
cin>>n;
for(ll i=1; i<=n; i++)
cin>>a[i];
for(ll i=1; i<=n; i++)
{
cin>>to[i];
in[to[i]]++;
}
queue<ll>q;
for(ll i=1; i<=n; i++)
if(!in[i])
q.push(i);
while(!q.empty())
{
ll x = q.front();
q.pop();
vis[x]=1;
u[x] = ++sz;
b[sz] = a[x];
ll z = to[x];
in[z]--;
if(!in[z])
q.push(z);
}
for(ll i=1; i<=n; i++)
{
if(vis[i])
continue;
sz++;
ll x = i;
while(!vis[x])
{
vis[x]=1;
u[x] = sz;
b[sz] += a[x];
x = to[x];
}
}
v.resize(sz+1);
for(ll i=1; i<=n; i++)
if(u[i] != u[to[i]])
{
v[u[to[i]]].push_back(u[i]);
not_root[u[i]]=1;
}
for(ll i=1; i<=sz; i++)
if(!not_root[i])
dfs0(i);
for(ll i=1; i<=sz; i++)
if(!not_root[i])
dfs1(i,0);
for(ll i=1; i<=n; i++)
cout<<ans[u[i]]<<" ";
cout<<"\n";
reset();
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
ll tt=1;
cin>>tt;
while(tt--)
solve();
return 0;
}
562768J - Hassan's Caffeine Routine
Author: Hassan_Fathi
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void hassan(){
int n , k;
cin >> n >> k;
vector<int> c(n);
for(auto &a : c)
cin >> a;
ll sm = 0;
for(auto &a : c){
sm += a;
}
cout << fixed << setprecision(10);
cout << double(sm) / n * k << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t; while(t --)
hassan();
}
Author: Hassan_Fathi
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void hassan(){
int n , m , x , y;
cin >> n >> m >> x >> y;
if(n > m){
swap(n , m);
swap(x , y);
}
ll res;
if(n == 1)
res = 1;
else if(n == 2){
if(y % 2 == 0)
m --;
res = (m + 1) / 2;
}
else if(n == 3 && m == 3)
res = (x == 2 && y == 2 ? 1 : 8);
else if(n >= 3)
res = (ll) n * m;
cout << res << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t; while(t --)
hassan();
}
https://codeforces.me/group/HcnH7vLzrr/contest/562768/submission/289688032
Can check where my implementation is wrong for D? there shouldnt be any overflow issue since i used python
not
Hassan_Fathi orz.
mii yet doo virttual contest
Thanks! I hope you enjoy the problems :)
Unable to view the contest
Are you in the Group ?
nice problemset thanks