Repository navigation
Expand file tree
/
Copy pathcodeupload.cpp
More file actions
171 lines (137 loc) · 4.15 KB
/
Copy pathcodeupload.cpp
File metadata and controls
171 lines (137 loc) · 4.15 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <bits/stdc++.h>
using namespace std;
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(nullptr);
#define Shikshak cout.tie(nullptr);
#define ll long long
#define lld long double
#define vll vector<ll>
#define co cout
#define e endl;
#define fi(i,x,n) for(ll i=x;i<n;i++)
#define fd(i,n,x) for(ll i=n;i>=x;i--)
#define pb push_back
#define print(v) for(auto &it:v)cout<<it<<" "; cout<<endl;
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define sortit(v) sort(v.begin(),v.end())
// Formula : a*b = lcm(a,b) * gcd(a,b)
// Formula to make pairs : (n*(n-1) )/2
// Always use map for hashing instead of unordered_map as it may gives TLE
// upper_bound(v.begin(),v.end(),U)
// Returns an iterator pointing to the first element that is greater than U.
// If no such element is found, returns last
// lower_bound(v.begin(),v.end(),L) gives you the pointer of the value greater than or equal to L
// lower_bound(v.begin(),v.end(),L) - v.begin() gives you the index of the value greater than or equal to L
// sort(v.begin(),v.end(),greater<ll>()); sorts the array in descending order
// a⊕b⊕a=b
// vec.insert(vec.begin(), x); to insert 'x' at the front of a vector
// INT_MAX:INT_MAX is typically 2147483647.
// INT_MAX is for int (usually 32-bit signed integer).
// INT_MIN : -2^31
// INT_MAX : 2^31 - 1
// LLONG_MAX: LLONG_MAX is typically 9223372036854775807.
// LLONG_MAX is for long long (usually 64-bit signed integer).
// SLIDING WINDOW OR TWO POINTER CONCEPT
// ll i=0,j=0;
// while(j<n)
// {
// while(condition not true) i++;
// }
// Maths Functions
ll gcd(ll a, ll b){if(b==0) return a; return gcd(b,a%b);}
ll lcm(ll a,ll b) {return (a*b)/gcd(a,b);}
ll prime(ll n){ if(n==1 || n==0) return 0; for(ll i=2;i*i<=n;i++) if(n%i==0) return 0;return 1;}
ll power(ll x, ll n){ll res=1;while(n){if(n&1) res*=x,n--;else x*=x,n/=2;}return res;}
ll ncr(ll n, ll r){ ll res=1; for(ll i=0;i<r;i++){res*=(n-i); res/=(i+1);} return res;}
ll npr(ll n, ll r){ ll res=1; for(ll i=0;i<r;i++){res*=(n-i); } return res;}
// Polynomial Rolling Hash Function
ll GetHash(string s)
{
ll p = 31;
ll m = 1e9+9;
ll hash_val = 0;
ll p_pow = 1;
for(auto &c:s)
{
hash_val = (hash_val + (c-'a'+1)*p_pow) % m;
p_pow = (p_pow*p)%m;
}
return hash_val;
}
// DSU code structure
class DisjointSet{
public:
vector<int> rank,size,parent;
DisjointSet(int n)
{
rank.resize(n+1,0);
parent.resize(n+1);
size.resize(n+1,1);
for(int i=0;i<n;i++)
{
parent[i]=i;
}
}
int findParent(int node)
{
if(parent[node]==node)
{
return node;
}
return parent[node] = findParent(parent[node]);
}
void unionByRank(int u, int v)
{
int u_parent = findParent(u);
int v_parent = findParent(v);
if(u_parent==v_parent) return ;
if(rank[u_parent]<rank[v_parent])
{
parent[u_parent] = v_parent;
}
else if(rank[u_parent]>rank[v_parent])
{
parent[v_parent] = u_parent;
}
else
{
parent[u_parent] = v_parent;
rank[v_parent]++;
}
}
void unionBySize(int u, int v)
{
int u_parent = findParent(u);
int v_parent = findParent(v);
if(u_parent==v_parent) return ;
if(size[u_parent]<size[v_parent])
{
parent[u_parent] = v_parent;
size[v_parent]+=size[u_parent];
}
else
{
parent[v_parent] = u_parent;
size[u_parent]+=size[v_parent];
}
}
};
// Constants
const ll mod = 1e9+7;
const lld pi= 3.141592653589793;
void solve()
{
ll n; cin>>n;
vll v(n); fi(i,0,n) cin>>v[i];
}
int main()
{
Code By Shikshak
ll t=1;
cin>>t;
while(t--)
{
solve();
}
}