#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vc vector
#define L cout<<'\n';
#define E cerr<<'\n';
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for (int i=a; i<b; ++i)
#define rev(i,a,b) for (int i=a-1; i>=b; --i)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setpr(x) cout<<setprecision(x)<<fixed
#define sz size()
#define seea(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
#define sees(s,n) for(int i=0;i<n;i++){int x; cin>>x; s.insert(x);}
const ll inf = INT_MAX;
const ld ep = 0.0000001;
const ld pi = acos(-1.0);
const ll mod = 1000000007;
int dp[1001][1001];
bool rem(ll a , ll b){return a%b;}
void init_code(){
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}
ll add(ll x, ll y){
   return (x+y)%mod;
}
ll multi(ll x , ll y){
   return (x*y)%mod;
}
ll power(ll x , ll y){
   x %= mod;
   ll res = 1;
   while(y > 0){
      if(y&1)res=multi(res,x);
      y=y>>1;
      x = multi(x,x);
   }
   return res;
}

ll inverse(ll n,ll p){
   return power(n,p-2);
}
int helper(unordered_map<int,vector<int>>&mp, vi &v,int ind,int prev){
   if(ind==v.size()) return 1;
   // cout<<ans
   if(dp[ind][prev]!=-1) return dp[ind][prev];
   int ans=0;
   for(auto it:mp[v[ind]]){
     if(it>prev)ans+=helper(mp,v,ind+1,it);
     ans%=mod;
   }
   return dp[ind][prev]=ans;
}
void solve(){
   int n;
   cin>>n;
   vi v(n);
   rep(i,0,n) cin>>v[i];
   unordered_map<int,vector<int>>mp;
   for(int i=1;i<=1000;i++){
         string s=to_string(i);
         int val=0;
         for(auto it:s){
            val+=it-'0';
         }
         mp[val].pb(i);
   }
   // vector<vector<int>>dp(1001,vector<int>(1001,-1));
   memset(dp,-1,sizeof(dp));
   cout<<helper(mp,v,0,0)<<endl;
}


signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
init_code();
   int t;cin >> t;while(t--)
   solve();
   return 0;
}

Google ✅
(C++)

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define MAXN 100001
#define INF 1e18+1

int solve(int matrixsizes , vector&arr , int start , int end , int diceroll)
{

   matrixsizes = matrixsizes*matrixsizes;
   unordered_map<int , int>mp;
   for(int i = 0 ; i < arr.size() ; i+=2)
   {
       mp[arr[i]] = arr[i+1];
   }
  vector<int>visited(matrixsizes+1 ,0);
    queue<pair<int, int>>q;
    q.push({start , 0});
    while(!q.empty())
    {
        int step = q.front().second;
        int pos = q.front().first;
        q.pop();
        if(pos == end) return step;
        for(int k = 1 ; k<= diceroll ; k++)
        {
            int loc = pos+k;
            if(loc>matrixsizes) break;
           
            if(visited[loc] == 1)continue;
           
            visited[loc] = 1;
            if(mp.find(loc) != mp.end())
            {
                q.push({mp[loc] , step+1});
            }
            else q.push({loc , step+1});
        }
    }
    return -1;
}
int main(){

#ifndef ONTLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);
#endif

int m, diceroll;
cin>>m>>diceroll;

int n ;

cin>>n;
vector<int>nums;
for(int i = 0 ; i < n ; i++)
{
  int x , y;
  cin>>x>>y;
  nums.push_back(x);
  nums.push_back(y);
}
int s ,e;
cin>>s>>e;;
cout<<solve(m , nums , s , e ,diceroll);

return 0;
}

Cisco ✅

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vc vector
#define L cout<<'\n';
#define E cerr<<'\n';
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for (int i=a; i<b; ++i)
#define rev(i,a,b) for (int i=a-1; i>=b; --i)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setpr(x) cout<<setprecision(x)<<fixed
#define sz size()
#define seea(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
#define sees(s,n) for(int i=0;i<n;i++){int x; cin>>x; s.insert(x);}
const ll inf = INT_MAX;
const ld ep = 0.0000001;
const ld pi = acos(-1.0);
const ll mod = 1000000007;
int dp[1001][1001];
bool rem(ll a , ll b){return a%b;}
void init_code(){
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}
ll add(ll x, ll y){
   return (x+y)%mod;
}
ll multi(ll x , ll y){
   return (x*y)%mod;
}
ll power(ll x , ll y){
   x %= mod;
   ll res = 1;
   while(y > 0){
      if(y&1)res=multi(res,x);
      y=y>>1;
      x = multi(x,x);
   }
   return res;
}

ll inverse(ll n,ll p){
   return power(n,p-2);
}
int helper(unordered_map<int,vector<int>>&mp, vi &v,int ind,int prev){
   if(ind==v.size()) return 1;
   // cout<<ans
   if(dp[ind][prev]!=-1) return dp[ind][prev];
   int ans=0;
   for(auto it:mp[v[ind]]){
     if(it>prev)ans+=helper(mp,v,ind+1,it);
     ans%=mod;
   }
   return dp[ind][prev]=ans;
}
void solve(){
   int n;
   cin>>n;
   vi v(n);
   rep(i,0,n) cin>>v[i];
   unordered_map<int,vector<int>>mp;
   for(int i=1;i<=1000;i++){
         string s=to_string(i);
         int val=0;
         for(auto it:s){
            val+=it-'0';
         }
         mp[val].pb(i);
   }
   // vector<vector<int>>dp(1001,vector<int>(1001,-1));
   memset(dp,-1,sizeof(dp));
   cout<<helper(mp,v,0,0)<<endl;
}


signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
init_code();
   int t;cin >> t;while(t--)
   solve();
   return 0;
}

Finding Arrays
Google ✅

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

vector<int> solve(int N, int M, vector<int>& ans) {
    vector<int> res;
    res.reserve(M);

    priority_queue<pair<long long, int>,
        vector<pair<long long, int>>, 
        greater<pair<long long, int>>> pq;

    for (int i = 1; i <= N; ++i) {
        pq.push(make_pair(0LL, i));
    }

    for (int it : ans) {
        pair<long long, int> top = pq.top();
        pq.pop();

        long long load = top.first;
        int x = top.second;

        res.push_back(x);
        pq.push(make_pair(load + it, x));
    }

    return res;
}

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int n=2,m=2;
    vector<int> ans={5,5};
    vector<int> ans1=solve(n,m,ans);
    for(int i=0;i<ans1.size();i++) cout<<ans1[i]<<" ";

}

Servers ✅

c++ 
#include <bits/stdc++.h> 
using namespace std; 
#define ll long long 

ll mod = 1e9 + 7, cc_total = 0; 

void dfs(vector<ll> adj[], vector<bool> &visited, ll src) 
{ 
    if (visited[src]) 
        return; 
    cc_total++; 
    // cout << src << " " << cc_total << "  vis\n"; 
    visited[src] = true; 
    for (auto i : adj[src]) 
    { 
        dfs(adj, visited, i); 
    } 
} 

void solve() 
{ 
    int n, m, x, y, total = 0, cap = 1; 
    cin >> n >> m; 
    vector<ll> adj[n + 1]; 
    vector<bool> visited(n + 1, false); 
    // for (int i = 1; i <= n; i++) 
    // { 
        // adj[i].push_back(i); 
    // } 
     
     
    for (int i = 0; i < m; i++) 
    { 
        cin >> x >> y; 
        adj[x].push_back(y); 
        adj[y].push_back(x); // for undirected 
    } 

    for (int j=1; j<=n; j++) 
    { 
        // for (auto j : i) 
        { 
            if (!visited[j]) 
            { 
                cc_total = 0; 
                dfs(adj, visited, j); 
                total++; 
                 
                cap = (cc_total*cap)%mod; 
                total %= mod; 
                // cout << endl; 
                cc_total = 0; 
            } 
        } 
    } 
    cout << total << " " << cap << "\n"; 
} 
int main() 
{ 
    int t = 1; 
    // #ifndef ONLINE_JUDGE 
    // freopen("input.txt", "r", stdin); 
    // freopen("output.txt", "w", stdout); 
    // #endif 
    cin >> t; 
    while (t--) 
    { 
        solve(); 
    } 
    return 0; 
} 

 

Fire Escape Routes✅

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

#define loop(i, a, n) for (lli i = (a); i < (n); ++i)
#define loopD(i, a, n) for (lli i = (a); i >= (n); --i)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define sz(a) ((lli)a.size())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define endl '\n'
#define fastio std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define pb push_back
#define pp pop_back()
#define fi first
#define si second
#define v(a) vector<int>(a)
#define vv(a) vector<vector<int>>(a)
#define present(c, x) ((c).find(x) != (c).end())
#define set_bits __builtin_popcountll
#define MOD 1000000007
#define int long long

typedef long long lli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<lli, lli> pll;
typedef pair<int, int> pii;
typedef unordered_map<int, int> umpi;
typedef map<int, int> mpi;
typedef vector<pii> vp;
typedef vector<lli> vll;
typedef vector<vll> vvll;

struct Line {
    int x1, y1, x2, y2;
    bool vertical() const { return x1 == x2; }
    bool horizontal() const { return y1 == y2; }
    bool diagonal() const { return abs(x2 - x1) == abs(y2 - y1); }
};

int N, K;
vector<Line> lines;
map<pair<int, int>, vector<int>> ptsMap;


void add(const Line& line, int idx) {
    int x1 = line.x1, y1 = line.y1;
    int x2 = line.x2, y2 = line.y2;

    if (line.vertical()) {
        int yStart = min(y1, y2);
        int yEnd = max(y1, y2);
        for(int y = yStart; y <= yEnd; y++) {
            ptsMap[{x1, y}].push_back(idx);
        }
    }
    else if (line.horizontal()) {
        int xStart = min(x1, x2);
        int xEnd = max(x1, x2);
        for(int x = xStart; x <= xEnd; x++) {
            ptsMap[{x, y1}].push_back(idx);
        }
    }
    else if (line.diagonal()) {
        int steps = abs(x2 - x1);
        int dx = (x2 - x1) / steps;
        int dy = (y2 - y1) / steps;
        for(int i = 0; i <= steps; i++) {
            int x = x1 + i * dx;
            int y = y1 + i * dy;
            ptsMap[{x, y}].push_back(idx);
        }
    }
}


int ff(int x1, int y1, int x2, int y2) {
    if(x1 == x2) return abs(y1 - y2);
    if(y1 == y2) return abs(x1 - x2);
    if(abs(x1 - x2) == abs(y1 - y2)) return abs(x1 - x2);
    return 0;
}

int solve(const pair<int, int>& pt, const vector<int>& lst) {
    vector<int> d;
    for(auto lIdx : lst) {
        const Line& ln = lines[lIdx];
        bool oneSided = (pt.first == ln.x1 && pt.second == ln.y1) || 
                        (pt.first == ln.x2 && pt.second == ln.y2);
        if(oneSided) {
            int ex = (pt.first == ln.x1 && pt.second == ln.y1) ? ln.x2 : ln.x1;
            int ey = (pt.first == ln.x1 && pt.second == ln.y1) ? ln.y2 : ln.y1;
            d.push_back(ff(pt.first, pt.second, ex, ey));
        }
        else {
            d.push_back(ff(pt.first, pt.second, ln.x1, ln.y1));
            d.push_back(ff(pt.first, pt.second, ln.x2, ln.y2));
        }
    }
    return d.empty() ? 0 : *min_element(d.begin(), d.end());
}


void solve() {
    cin >> N;
    lines.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> lines[i].x1 >> lines[i].y1 >> lines[i].x2 >> lines[i].y2;
        add(lines[i], i);
    }
    cin >> K;

    int total = 0;
    for(auto &[pt, lst] : ptsMap) {
        if(sz(lst) == K) {
            total += solve(pt, lst);
        }
    }
    cout << total << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    solve();
    return 0;
}

Magic Stars ✅
TCS Codevita
Source : ishaan