Blog entries - Codeforces

Solution

Implementation

C++

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int> 
#define fr first
#define sc second 
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void ninjamayank(){
    ll n,k;
    cin >> n >> k;
    vector<vector<ll>> grid(n,vector<ll>(n));
    for(ll i = 0;i < n;i++){
        input(grid[i]);
    }
    ll low = 0, high = 1e18;
    ll ans = -1;
    while(low <= high){
        ll mid = (low + high) / 2;
        vector<vector<ll>> mat(n,vector<ll>(n));
        for(ll i = 0;i < n;i++){
            for(ll j = 0;j < n;j++){
                mat[i][j] = (grid[i][j] >= mid);
            }
        }
        vector<vector<ll>> pref(n,vector<ll>(n));
        for(ll i = 0;i < n;i++){
            for(ll j = 0;j < n;j++){
                pref[i][j] = mat[i][j] + (i - 1 >= 0 ? pref[i - 1][j] : 0) + (j - 1 >= 0 ? pref[i][j - 1] : 0) - (i - 1 >= 0 && j - 1 >= 0 ? pref[i - 1][j - 1] : 0);
            }
        }
        bool flag = false;
        for(ll i = k - 1;i < n;i++){
            for(ll j = k - 1;j < n;j++){
                ll sum = pref[i][j] - (i - k >= 0 ? pref[i - k][j] : 0) - (j - k >= 0 ? pref[i][j - k] : 0) + (i - k >= 0 && j - k >= 0 ? pref[i - k][j - k] : 0);
                if(sum == k * k){
                    flag = 1;
                    break;
                }
            }
        }
        if(flag){
            ans = mid;
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }
    cout << ans << nline;
}
int main(){
    // #ifndef ONLINE_JUDGE
    //     //for getting input from input1.txt
    //     freopen("input1.txt", "r", stdin);
    //     //for getting output from output1.txt
    //     freopen("output1.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); // remove in problems with online query
    int testcase = 1;
    // cin >> testcase;
    int gtc = 1;
    while(testcase--){
        //cout << "Case #" << gtc << ": ";
        ninjamayank();
        gtc++;
    }
}

Solution

Implementation

C++

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <string>
#include <vector>
 
using namespace std;
 
const int MAXN = 210;
const int MAXF = 210;
 
int N, F;
int DuM[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
 
int Init[MAXN][MAXF + 1];
int Mat[MAXN][MAXF + 1];
 
inline int get_day() {
  int d, m;
  scanf("%d %d", &d, &m);
  --d, --m;
 
  for (int i = 0; i < m; ++i) d += DuM[i];
 
  return d;
}
 
int Sol5[MAXF];
int Sol73[MAXF];
 
int Invert[100];
int superOk = true;
 
void gauss_solve(int p, int *Sol) {
  for (int i = 0; i < N; ++i)
    for (int j = 0; j <= F; ++j) Mat[i][j] = Init[i][j] % p;
 
  Invert[0] = 0;
 
  for (int i = 1; i < p; ++i)
    for (int j = 1; j < p; ++j)
      if ((i * j) % p == 1) Invert[i] = j;
 
  int R = 0;
 
  for (int s = 0; s < F; ++s) {
    int index = -1;
 
    for (int i = R; index == -1 && i < N; ++i)
      if (Mat[i][s] != 0) index = i;
 
    if (index == -1) continue;
    if (R != index)
      for (int i = 0; i <= F; ++i) swap(Mat[R][i], Mat[index][i]);
 
    int temp_mat = Invert[Mat[R][s]];
    for (int i = 0; i <= F; ++i) Mat[R][i] = (Mat[R][i] * temp_mat) % p;
 
    for (int i = 0; i < N; ++i)
      if (i != R) {
        int coef = Mat[i][s];
 
        for (int j = 0; j <= F; ++j) {
          Mat[i][j] -= coef * Mat[R][j];
          Mat[i][j] %= p;
          if (Mat[i][j] < 0) Mat[i][j] += p;
        }
      }
 
    ++R;
  }
 
  for (int i = 0; i < N; ++i) {
    int first = -1;
 
    for (int j = 0; j < F; ++j)
      if (Mat[i][j] != 0) {
        first = j;
        break;
      }
 
    if (first == -1) {
      if (Mat[i][F] != 0) {
        superOk = false;
        return;
      }
      continue;
    }
 
    Sol[first] = Mat[i][F];
  }
}
 
int main(void) {
  scanf("%d %d", &N, &F);
 
  for (int i = 0; i < N; ++i) {
    int a = get_day();
    int b = get_day();
 
    for (int j = 0; j < F; ++j) scanf("%d", Init[i] + j);
 
    Init[i][F] = ((b - a) % 365 + 365) % 365;
  }
 
  gauss_solve(5, Sol5);
  gauss_solve(73, Sol73);
 
  if (!superOk) {
    printf("-1\n");
    return (0 - 0);
  }
 
  for (int i = 0; i < F; ++i) {
    int tmp = (146 * Sol5[i] + 220 * Sol73[i]) % 365;
    if (tmp == 0) tmp = 365;
    printf("%d\n", tmp);
  }
 
  return (0);
}

Solution

Implementation

C++

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int> 
#define fr first
#define sc second 
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
vector<ll> basis(62);
ll sz = 0;
 
void insertVector(ll mask) {
    for (ll i = 61; i >= 0; i--) {
        if((mask & (1ll << i)) == 0) continue;
        if (!basis[i]){
            basis[i] = mask;
            ++sz;
            return;
        }
        mask ^= basis[i];
    }
}
 
void ninjamayank(){
    ll n;
    cin >> n;
    vector<ll> v(n);input(v);
    ll xr = 0;
    for(ll i = 0;i < n;i++){
        xr ^= v[i];
    }
    for(ll i = 0;i < n;i++){
        ll num = 0;
        for(ll mask = 0;mask < 62;mask++){
            if(xr&(1ll << mask)) continue;
            if(v[i]&(1ll << mask)){
                num ^= (1ll << mask);
            }
        }
        insertVector(num);
    }
    ll ans = 0;
    for(ll i = 61;i >= 0;i--){
        if(ans&(1ll << i)) continue;
        ans ^= basis[i];
    }
    for(ll i = 0;i < 62;i++){
        if(xr&(1ll << i)) ans ^= (1ll << i);
    }
    cout << ans + (xr ^ ans);
}
int main(){
    // #ifndef ONLINE_JUDGE
    //     //for getting input from input1.txt
    //     freopen("input1.txt", "r", stdin);
    //     //for getting output from output1.txt
    //     freopen("output1.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); // remove in problems with online query
    int testcase = 1;
    // cin >> testcase;
    int gtc = 1;
    while(testcase--){
        //cout << "Case #" << gtc << ": ";
        ninjamayank();
        gtc++;
    }
}

Solution

Implementation

Python

import sys, threading
import math
from os import path
from collections import deque, defaultdict, Counter
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
from random import randint
from heapq import *
from array import array
from types import GeneratorType
 
 
def readInts():
    x = list(map(int, (sys.stdin.readline().rstrip().split())))
    return x[0] if len(x) == 1 else x
 
 
def readList(type=int):
    x = sys.stdin.readline()
    x = list(map(type, x.rstrip('\n\r').split()))
    return x
 
 
def readStr():
    x = sys.stdin.readline().rstrip('\r\n')
    return x
 
 
write = sys.stdout.write
read = sys.stdin.readline
 
 
MAXN = 1123456
 
 
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
 
 
class mydict:
    def __init__(self, func=lambda: 0):
        self.random = randint(0, 1 << 32)
        self.default = func
        self.dict = {}
 
    def __getitem__(self, key):
        mykey = self.random ^ key
        if mykey not in self.dict:
            self.dict[mykey] = self.default()
        return self.dict[mykey]
 
    def get(self, key, default):
        mykey = self.random ^ key
        if mykey not in self.dict:
            return default
        return self.dict[mykey]
 
    def __setitem__(self, key, item):
        mykey = self.random ^ key
        self.dict[mykey] = item
 
    def getkeys(self):
        return [self.random ^ i for i in self.dict]
 
    def __str__(self):
        return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'
 
 
def lcm(a, b):
    return (a*b)//(math.gcd(a,b))
 
 
def mod(n):
    return n%(1000000007)
 
def area(p1, p2, p3):
 
    cur = (p2[0] - p1[0])*(p3[1] - p1[1]) - (p2[1] - p1[1])*(p3[0] - p1[0])
    return cur
 
 
def convex_hull(points):
 
    points = list(set(points))
    points.sort()
    # print(points)
 
    n = len(points)
 
    if n < 3:
        return points
 
    hull = []
    for i in range(n):
 
        while len(hull) > 1 and area(hull[-2], hull[-1], points[i]) <= 0:
            hull.pop()
 
        hull.append(points[i])
 
    ln = len(hull)
 
    for i in range(n-2, -1, -1):
 
        while len(hull) > ln and area(hull[-2], hull[-1], points[i]) <= 0:
            hull.pop()
 
        hull.append(points[i])
 
    hull.pop()
 
    return hull
 
 
def solve(t):
    # print(f'Case #{t}: ', end = '')
    n = readInts()
    ar = []
    for _ in range(n):
        u, v = readInts()
        ar.append((u, v))
 
    chull = convex_hull(ar)
    m = len(chull)
 
    ans = sorted(chull)
    print(m)
    for x, y in ans:
        print(x, y)
 
 
    area = 0
    total_bndr = 0
    for i in range(m):
        x1, y1 = chull[i%m]
        x2, y2 = chull[(i+1)%m]
        area += (x1*y2) - (x2*y1)
        total_bndr += math.gcd(abs(x2-x1), abs(y2-y1))
 
    area = abs(area)
    total_lat = (area - total_bndr)//2 + 1

    cost = float('inf')
    for i in range(m):
        a1 = 0
        pref_bndr = 0
        x1, y1 = chull[i]
        cur = 0
        for j in range(i+1, m):
 
            if i == 0 and j == m-1:
                break
 
            x2, y2 = chull[j]
            x_prev, y_prev = chull[j-1]
            cur += (y2*x_prev) - (x2*y_prev)
            
            g = math.gcd(abs(x2-x_prev), abs(y2-y_prev))
            pref_bndr += g
 
            cur_bndr = math.gcd(abs(x2-x1), abs(y2-y1))
 
            if j-1 != i:
                a1 = cur + ((x2*y1) - (x1*y2))
 
                a1 = abs(a1)
 
                n1 = (a1 - pref_bndr - cur_bndr)//2 + 1
                n2 = total_lat - n1 - (cur_bndr-1)
 
                cost = min(cost, abs(n2-n1))
 
 
    print(cost)
 
 
def main():
    t = 1
    if path.exists("/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt"):
        sys.stdin = open("/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt", 'r')
        sys.stdout = open("/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/output.txt", 'w')
    # sys.setrecursionlimit(100000) 
    t = readInts()
    for i in range(t):
        solve(i+1)
 
 
if __name__ == '__main__':
    main()

Solution

Implementation

C++

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int> 
#define fr first
#define sc second 
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
vector<ll> tin(N), tout(N);
ll timer = 0;
 
void euler(ll u, ll p, vector<vector<ll>> &g){
    tin[u] = timer++;
    for(auto &child : g[u]){
        if(child == p) continue;
        euler(child,u,g);
    }
    tout[u] = timer++;
}
 
bool check(ll l, ll r){
    return (tin[l] < tin[r] && tout[l] > tout[r]);
}
 
void ninjamayank(){
    ll n,q;
    cin >> n >> q;
    vector<vector<ll>> g(n);
    vector<pair<ll, ll>> queries;
    while(q--){
        ll type,l,r;
        cin >> type >> l >> r;
        --l;--r;
        if(type == 1){
            g[l].pb(r);
            g[r].pb(l);
        }else{
            queries.pb({l,r});
        }
    }
    euler(0,-1,g);
    for(auto &p : queries){
        ll l = p.fr, r = p.sc;
        cout << (check(l,r) ? "Yes" : "No") << nline;
    }
}
int main(){
    // #ifndef ONLINE_JUDGE
    //     //for getting input from input1.txt
    //     freopen("input1.txt", "r", stdin);
    //     //for getting output from output1.txt
    //     freopen("output1.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); // remove in problems with online query
    int testcase = 1;
    // cin >> testcase;
    int gtc = 1;
    while(testcase--){
        //cout << "Case #" << gtc << ": ";
        ninjamayank();
        gtc++;
    }
}

Solution

Implementation

Solution

Implementation

Solution

Implementation

C++

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int> 
#define fr first
#define sc second 
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct segtree{
    vector<ll> seg;
    vector<ll> lazy;
    vector<bool> cLazy;
    ll size;
    void init(ll n){
        size = 1;
        while(size < n){
            size *= 2;
        }
        seg.assign(4*size,0ll);
        lazy.assign(4*size,0ll);
        cLazy.assign(4*size,false);
    }
    ll apply(ll x1, ll x2){
        return (x1 + x2);
    }
    void propagate(ll ind, ll low, ll high)
    {
        if(low != high)
        {
            cLazy[2*ind + 1] = 1;
            cLazy[2*ind + 2] = 1;
            lazy[2*ind + 1] += lazy[ind];
            lazy[2*ind + 2] += lazy[ind];
        }
        seg[ind] += lazy[ind];
        lazy[ind] = 0;
        cLazy[ind] = 0;
    }
    void build(vector<ll> &v, ll ind, ll low, ll high){
        if(low == high){
            seg[ind] = v[low];
            return;
        }
        ll mid = (low + high) >> 1;
        build(v,2*ind + 1,low,mid);
        build(v,2*ind + 2,mid + 1,high);
        seg[ind] = apply(seg[2*ind + 1],seg[2*ind + 2]);
    }
    void update(ll ind, ll low, ll high, ll l, ll r, ll val){
        if(cLazy[ind]){
            propagate(ind,low,high);
        }
        if(high < l || low > r){
            return;
        }
        if(l <= low && r >= high){
            cLazy[ind] = 1;
            lazy[ind] += val;
            propagate(ind,low,high);
            return;
        }
        ll mid = (low + high) >> 1;
        update(2*ind + 1,low,mid,l,r,val);
        update(2*ind + 2,mid + 1,high,l,r,val);
        seg[ind] = apply(seg[2*ind + 1],seg[2*ind + 2]);
    }
    ll query(ll ind, ll low, ll high, ll l, ll r){
        if(cLazy[ind]){
            propagate(ind,low,high);
        }
        if(high < l || low > r){
            return 0;
        }
        if(low >= l && high <= r){
            return seg[ind];
        }
        ll mid = (low + high) >> 1;
        ll left = query(2*ind + 1,low,mid,l,r);
        ll right = query(2*ind + 2,mid + 1,high,l,r);
        return apply(left,right);
    }
};
 
void ninjamayank(){
    ll n;
    cin >> n;
    vector<ll> v(n);input(v);
    segtree st1;
    st1.init(n + 1);
    map<ll, ll> mp;
    for(ll i = 0;i < n;i++){
        mp[v[i]] = 0;
    }
    ll id = 1;
    for(auto &it : mp){
        it.sc = id++;
    }
    for(ll i = 0;i < n;i++){
        v[i] = mp[v[i]];
    }
    vector<pair<ll, ll>> res(n);
    for(ll i = 0;i < n;i++){
        res[i].fr = st1.query(0,0,n,v[i] + 1,n);
        st1.update(0,0,n,v[i],v[i],1);
    }
    segtree st2;
    st2.init(n + 1);
    for(ll i = n - 1;i >= 0;i--){
        res[i].sc = st2.query(0,0,n,v[i] + 1,n);
        st2.update(0,0,n,v[i],v[i],1);
    }
    for(auto &p : res){
        cout << p.fr << " " << p.sc << nline;
    }
}
int main(){
    // #ifndef ONLINE_JUDGE
    //     //for getting input from input1.txt
    //     freopen("input1.txt", "r", stdin);
    //     //for getting output from output1.txt
    //     freopen("output1.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); // remove in problems with online query
    int testcase = 1;
    cin >> testcase;
    int gtc = 1;
    while(testcase--){
        //cout << "Case #" << gtc << ": ";
        ninjamayank();
        gtc++;
    }
}