#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int solve(int n, int m, int x, vector<int>& a) {
int rem = m % x;
if (rem == 0) {
return m % MOD;
}
int minAdd = -1;
for (int i = 0; i < n; i++) {
int add = a[i];
if ((m + add) % x == 0) {
if (minAdd == -1 || add < minAdd) {
minAdd = add;
}
}
}
if (minAdd == -1) {
return -1;
}
return (m + minAdd) % MOD;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m, x;
cin >> n >> m >> x;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int res =solve(n, m, x, a);
cout << res << endl;
}
return 0;
}
Greedy power โ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
int32_t main(){
ll n,m;
cin>>n>>m;
vector<ll> a(n);
vector<ll> b(m);
vector<ll> pre(n+1);
for(int i=0;i<n;i++){
cin>>a[i];
pre[i+1]=pre[i]+a[i];
}
for(int i=0;i<m;i++){
cin>>b[i];
}
ll k=(1LL<<m)-1;
ll dp[n+1][k+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j]);
for(int l=0;l<m;l++){
if((1LL<<l)&j){
}
else{
ll next=(1LL<<l)|j,idx=i+b[l]-1;
if(idx>=0 and idx<=n)
dp[idx][next]=max(dp[idx][next],dp[i-1][j]+pre[idx]-pre[i-1]);
}
}
}
}
ll ans=0;
for(int i=0;i<=n;i++){
ans=max(dp[i][k],ans);
}
cout<<ans<<endl;
return 0;
}
Seat Bookingโ
๐1
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> solve(vector<int> &v){
int n=v.size();
vector<bool> found(n+1,false);
int curr=1;
vector<vector<int>> ans;
for(auto x:v){
found[x]=true;
vector<int> temp;
if(found[curr]){
while(curr<=n && found[curr] ){
temp.push_back(curr);
curr++;
}
}
else{
temp.push_back(-1);
}
ans.push_back(temp);
}
return ans;
}
int32_t main(){
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++){
cin>>v[i];
}
vector<vector<int>> ans=solve(v);
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans[i].size();j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
}
Amazon โ
using namespace std;
#define int long long
vector<vector<int>> solve(vector<int> &v){
int n=v.size();
vector<bool> found(n+1,false);
int curr=1;
vector<vector<int>> ans;
for(auto x:v){
found[x]=true;
vector<int> temp;
if(found[curr]){
while(curr<=n && found[curr] ){
temp.push_back(curr);
curr++;
}
}
else{
temp.push_back(-1);
}
ans.push_back(temp);
}
return ans;
}
int32_t main(){
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++){
cin>>v[i];
}
vector<vector<int>> ans=solve(v);
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans[i].size();j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
}
Amazon โ
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> msk(1024,-1);
void digits(ll num1) {
string str1 = to_string(num1);
set<ll>s;
for (char digit : str1) {
ll d=digit-'0';
s.insert(d);
}
ll val=0;
for(auto it:s) val+=(1<<it);
msk[val]=max(msk[val],num1);
}
ll solution(vector<ll>& A) {
for(auto &it:msk) it=-1;
ll ans=-1;
for(auto it:A) digits(it);
for(ll i=1;i<1024;i++){
if(msk[i]==-1) continue;
for(ll j=i+1;j<1024;j++){
if(msk[j]==-1) continue;
ll fl=0;
for(ll k=0;k<10;k++){
if((1<<k)&i){
if((1<<k)&j){
fl=1;
continue;
}
}
}
if(fl) continue;
ans=max(ans,msk[i]+msk[j]);
}
}
return ans;
}
Microsoft โ
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
multiset<pair<int, int>> s;
for (int i = 0; i < n; i++) {
s.insert({v[i], i});
}
int ans = 0;
vector<bool> vis(n, false);
while (!s.empty()) {
auto [x, i] = *prev(s.end());
s.erase(prev(s.end()));
ans += x;
vis[i] = true;
int left = (i - 1 + n) % n;
int right = (i + 1) % n;
while (vis[right]) {
right = (right + 1) % n;
}
vis[right] = true;
s.erase({v[right], right});
while (vis[left]) {
left = (left - 1 + n) % n;
}
vis[left] = true;
s.erase({v[left], left});
}
cout << ans << endl;
}
Kickdrum โ
using namespace std;
#define int long long
int32_t main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
multiset<pair<int, int>> s;
for (int i = 0; i < n; i++) {
s.insert({v[i], i});
}
int ans = 0;
vector<bool> vis(n, false);
while (!s.empty()) {
auto [x, i] = *prev(s.end());
s.erase(prev(s.end()));
ans += x;
vis[i] = true;
int left = (i - 1 + n) % n;
int right = (i + 1) % n;
while (vis[right]) {
right = (right + 1) % n;
}
vis[right] = true;
s.erase({v[right], right});
while (vis[left]) {
left = (left - 1 + n) % n;
}
vis[left] = true;
s.erase({v[left], left});
}
cout << ans << endl;
}
Kickdrum โ
#include <bits/stdc++.h>
#define ll long long
using namespace std;
string mergePalindrome(string&a,string&b)
{
ll n=a.length();
ll m=b.length();
unordered_map<char,ll> m1,m2;
for(char it:a) m1[it]++;
for(char it:b) m2[it]++;
string mid="",ans="";
for (char i='a';i<='z';i++)
{
if(m1[i]%2 and m2[i]%2 and mid.length()<=1) mid=string(2,i);
if((m1[i]%2 or m2[i]%2) and mid.length()==0) mid=i;
ans+=string((m1[i]/2+m2[i]/2),i);
}
string tt=ans;
if (mid.length()==2)
{
tt+=mid[0];
ans+=mid[0];
sort(begin(ans),end(ans));
tt=ans+string(rbegin(ans),rend(ans));
}
else tt+=mid+string(rbegin(ans),rend(ans));
return tt;
}
signed main()
{
string s,t; cin>>s>>t;
cout<<solve(s,t);
return 0;
}
Merging palindromes โ
#define ll long long
using namespace std;
string mergePalindrome(string&a,string&b)
{
ll n=a.length();
ll m=b.length();
unordered_map<char,ll> m1,m2;
for(char it:a) m1[it]++;
for(char it:b) m2[it]++;
string mid="",ans="";
for (char i='a';i<='z';i++)
{
if(m1[i]%2 and m2[i]%2 and mid.length()<=1) mid=string(2,i);
if((m1[i]%2 or m2[i]%2) and mid.length()==0) mid=i;
ans+=string((m1[i]/2+m2[i]/2),i);
}
string tt=ans;
if (mid.length()==2)
{
tt+=mid[0];
ans+=mid[0];
sort(begin(ans),end(ans));
tt=ans+string(rbegin(ans),rend(ans));
}
else tt+=mid+string(rbegin(ans),rend(ans));
return tt;
}
signed main()
{
string s,t; cin>>s>>t;
cout<<solve(s,t);
return 0;
}
Merging palindromes โ
๐1
#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
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
๐2
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
\#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) ((int)a.size())
#define YES cout << "YES";
#define NO cout << "NO";
#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 game {
int start;
int end;
string type;
};
bool solve(vector<int>& dieRolls, unordered_map<int, int>& board, int finalPos) {
int position = 1;
for (int roll : dieRolls) {
if (position + roll <= 100) {
position += roll;
}
while (board.find(position) != board.end()) {
position = board[position];
}
}
if (board.find(position) != board.end()) {
return false;
}
return position == finalPos;
}
void solve()
{
int N;
cin >> N;
vector<game> snakesLadders;
unordered_map<int, int> board;
for (int i = 0; i < N; ++i) {
int start, end;
cin >> start >> end;
game sl;
sl.start = start;
sl.end = end;
if (start > end) {
sl.type = "Snake";
} else {
sl.type = "Ladder";
}
snakesLadders.push_back(sl);
board[start] = end;
}
vector<int> remainingInput;
int num;
while (cin >> num) {
remainingInput.push_back(num);
}
if (remainingInput.empty()) {
cout << "Not reachable";
return;
}
int finalPos = remainingInput.back();
remainingInput.pop_back();
vector<int> dieRolls = remainingInput;
if (solve(dieRolls, board, finalPos)) {
cout << "Not affected";
return;
}
for (size_t i = 0; i < snakesLadders.size(); ++i) {
game& sl = snakesLadders[i];
board.erase(sl.start);
int newStart = sl.end;
int newEnd = sl.start;
string newType = (sl.type == "Snake") ? "Ladder" : "Snake";
if (newStart == 1 || board.find(newStart) != board.end()) {
board[sl.start] = sl.end;
continue;
}
board[newStart] = newEnd;
if (solve(dieRolls, board, finalPos)) {
cout << newType << " " << newStart << " " << newEnd;
return ;
}
board.erase(newStart);
board[sl.start] = sl.end;
}
cout << "Not reachable";
return ;
}
int32_t main()
{
int tc = 1;
// cin >> tc;
while (tc--)
{
solve();
}
return 0;
}
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) ((int)a.size())
#define YES cout << "YES";
#define NO cout << "NO";
#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 game {
int start;
int end;
string type;
};
bool solve(vector<int>& dieRolls, unordered_map<int, int>& board, int finalPos) {
int position = 1;
for (int roll : dieRolls) {
if (position + roll <= 100) {
position += roll;
}
while (board.find(position) != board.end()) {
position = board[position];
}
}
if (board.find(position) != board.end()) {
return false;
}
return position == finalPos;
}
void solve()
{
int N;
cin >> N;
vector<game> snakesLadders;
unordered_map<int, int> board;
for (int i = 0; i < N; ++i) {
int start, end;
cin >> start >> end;
game sl;
sl.start = start;
sl.end = end;
if (start > end) {
sl.type = "Snake";
} else {
sl.type = "Ladder";
}
snakesLadders.push_back(sl);
board[start] = end;
}
vector<int> remainingInput;
int num;
while (cin >> num) {
remainingInput.push_back(num);
}
if (remainingInput.empty()) {
cout << "Not reachable";
return;
}
int finalPos = remainingInput.back();
remainingInput.pop_back();
vector<int> dieRolls = remainingInput;
if (solve(dieRolls, board, finalPos)) {
cout << "Not affected";
return;
}
for (size_t i = 0; i < snakesLadders.size(); ++i) {
game& sl = snakesLadders[i];
board.erase(sl.start);
int newStart = sl.end;
int newEnd = sl.start;
string newType = (sl.type == "Snake") ? "Ladder" : "Snake";
if (newStart == 1 || board.find(newStart) != board.end()) {
board[sl.start] = sl.end;
continue;
}
board[newStart] = newEnd;
if (solve(dieRolls, board, finalPos)) {
cout << newType << " " << newStart << " " << newEnd;
return ;
}
board.erase(newStart);
board[sl.start] = sl.end;
}
cout << "Not reachable";
return ;
}
int32_t main()
{
int tc = 1;
// cin >> tc;
while (tc--)
{
solve();
}
return 0;
}
โค1๐1
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#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) ((int)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 Flight {
string src;
string to;
int dt;
int at;
int cost;
};
int parse_time(const string& time_str) {
int hour = stoi(time_str.substr(0, 2));
int minute = stoi(time_str.substr(3, 2));
string am_pm = time_str.substr(5, 2);
if (am_pm == "Am") {
if (hour == 12) hour = 0;
} else if (am_pm == "Pm") {
if (hour != 12) hour += 12;
}
return hour * 60 + minute;
}
void solve()
{
int N;
cin >> N;
vector<Flight> fff(N);
unordered_map<string, vector<Flight>> mp;
for (int i = 0; i < N; ++i) {
string src, to, des, arrival_str;
int cost;
cin >> src >> to >> des >> arrival_str >> cost;
int dt = parse_time(des);
int at = parse_time(arrival_str);
Flight ff = {src, to, dt, at, cost};
fff[i] = ff;
mp[src].push_back(ff);
}
string src, des;
cin >> src >> des;
string edes, last;
cin >> edes >> last;
int earliest_dt = parse_time(edes);
int latest_at = parse_time(last);
typedef tuple<int, int, string> State;
priority_queue<State, vector<State>, greater<State>> pq;
for (const auto& ff : mp[src]) {
if (ff.dt >= earliest_dt) {
if (ff.at <= latest_at) {
pq.emplace(ff.cost, ff.at, ff.to);
}
}
}
unordered_map<string, int> ans;
unordered_map<string, int> at;
while (!pq.empty()) {
int cost_so_far, current_at;
string current_city;
tie(cost_so_far, current_at, current_city) = pq.top();
pq.pop();
if (ans.find(current_city) != ans.end()) {
if (cost_so_far > ans[current_city]) continue;
if (cost_so_far == ans[current_city] && current_at >= at[current_city]) continue;
}
ans[current_city] = cost_so_far;
at[current_city] = current_at;
if (current_city == des) {
cout << cost_so_far;
return ;
}
for (const auto& ff : mp[current_city]) {
if (ff.dt >= current_at) {
if (ff.dt >= earliest_dt && ff.at <= latest_at) {
int new_cost = cost_so_far + ff.cost;
pq.emplace(new_cost, ff.at, ff.to);
}
}
}
}
cout << "Impossible";
return ;
}
int32_t main()
{
int tc = 1;
// cin >> tc;
while (tc--)
{
solve();
}
return 0;
}
Flight optimizationโ
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) ((int)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 Flight {
string src;
string to;
int dt;
int at;
int cost;
};
int parse_time(const string& time_str) {
int hour = stoi(time_str.substr(0, 2));
int minute = stoi(time_str.substr(3, 2));
string am_pm = time_str.substr(5, 2);
if (am_pm == "Am") {
if (hour == 12) hour = 0;
} else if (am_pm == "Pm") {
if (hour != 12) hour += 12;
}
return hour * 60 + minute;
}
void solve()
{
int N;
cin >> N;
vector<Flight> fff(N);
unordered_map<string, vector<Flight>> mp;
for (int i = 0; i < N; ++i) {
string src, to, des, arrival_str;
int cost;
cin >> src >> to >> des >> arrival_str >> cost;
int dt = parse_time(des);
int at = parse_time(arrival_str);
Flight ff = {src, to, dt, at, cost};
fff[i] = ff;
mp[src].push_back(ff);
}
string src, des;
cin >> src >> des;
string edes, last;
cin >> edes >> last;
int earliest_dt = parse_time(edes);
int latest_at = parse_time(last);
typedef tuple<int, int, string> State;
priority_queue<State, vector<State>, greater<State>> pq;
for (const auto& ff : mp[src]) {
if (ff.dt >= earliest_dt) {
if (ff.at <= latest_at) {
pq.emplace(ff.cost, ff.at, ff.to);
}
}
}
unordered_map<string, int> ans;
unordered_map<string, int> at;
while (!pq.empty()) {
int cost_so_far, current_at;
string current_city;
tie(cost_so_far, current_at, current_city) = pq.top();
pq.pop();
if (ans.find(current_city) != ans.end()) {
if (cost_so_far > ans[current_city]) continue;
if (cost_so_far == ans[current_city] && current_at >= at[current_city]) continue;
}
ans[current_city] = cost_so_far;
at[current_city] = current_at;
if (current_city == des) {
cout << cost_so_far;
return ;
}
for (const auto& ff : mp[current_city]) {
if (ff.dt >= current_at) {
if (ff.dt >= earliest_dt && ff.at <= latest_at) {
int new_cost = cost_so_far + ff.cost;
pq.emplace(new_cost, ff.at, ff.to);
}
}
}
}
cout << "Impossible";
return ;
}
int32_t main()
{
int tc = 1;
// cin >> tc;
while (tc--)
{
solve();
}
return 0;
}
Flight optimizationโ
#include <bits/stdc++.h>omega prime
using namespace std;
#define ll long long
const ll M = 1e9+7 ;
int main() {
ll n;cin>>n ;
vector<ll> v(31) ;
for(ll i = 1;i<=n;i++){
ll x;cin>>x ;
v[x]++ ;
}
vector<ll> p ;
for(ll i = 2;i<=30;i++){
bool ch = 1 ;
for(ll j = 2;j*j<=i;j++){
if(i%(j*j)==0)ch = 0 ;
}
if(ch)p.push_back(i) ;
}
ll one = 1 ;
while(v[1]){
one = one*2%M ;
v[1]-- ;
}
n = p.size() ;
ll ans = 0 ;
for(ll i = 1;i<(1ll<<n);i++){
ll pro = 1 ;
ll tot = 1 ;
bool ch = 1 ;
for(ll j =0;j<n;j++){
if((1ll<<j)&i){
if(__gcd(pro,p[j])!=1){
ch = 0 ;
break;
}
pro = pro*p[j] ;
tot = tot*v[p[j]]%M ;
}
}
tot = tot*(one)%M ;
if(ch){
ans += tot ;
ans %= M ;
}
}
cout<<(ans+M)%M<<endl;
return 0;
}
}
media .netโ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool prime[100005];
int dp[100005];
ll answer;
bool visited[100005];
vector<int>adjacent[100005];
void dfs1(int u)
{
visited[u] = true;
int sum = prime[u] ? 0 : 1;
for(int i = 0 ; i < adjacent[u].size() ; i++)
{
int v = adjacent[u][i];
if(!visited[v])
{
dfs1(v);
sum += dp[v];
}
}
dp[u] = sum;
if(prime[u]) dp[u] = 0;
}
void dfs2(int u, int p, int dv)
{
visited[u] = true;
if(prime[u])
{
vector<ll>pp;
ll sum = dv;
pp.push_back(dv);
for(int i = 0 ; i < adjacent[u].size() ; i++)
{
int v = adjacent[u][i];
if(!visited[v] && v != p)
{
dfs2(v, u, 0);
pp.push_back(dp[v]);
sum += dp[v];
}
}
ll val = 0;
for(int i = 0 ; i < pp.size() ; i++)
{
val += (sum-pp[i])*pp[i];
}
val /= 2;
answer += val;
answer += sum;
}
else
{
for(int i = 0 ; i < adjacent[u].size() ; i++)
{
int v = adjacent[u][i];
if(!visited[v] && v != p)
{
dfs2(v, u, dv + dp[u] - dp[v]);
}
}
}
}
void Sieve()
{
for(int i = 1 ; i <= 100000 ; i++)
{
prime[i] = true;
}
prime[1] = false;
for(int i = 2 ; i*i <= 100000 ; i++)
{
if(prime[i])
{
for(int j = i*i ; j <= 100000 ; j += i)
{
prime[j] = false;
}
}
}
}
int main(){
Sieve();
int n;
cin>>n;
assert(1 <= n && n <= 100000);
for(int i = 0 ; i < n - 1 ; i++)
{
int u,v;
cin>>u>>v;
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
adjacent[u].push_back(v);
adjacent[v].push_back(u);
}
dfs1(1);
for(int i = 1 ; i <= n ; i++) visited[i] = false;
dfs2(1,0,0);
cout<<answer<<endl;
}
prime pairsโ
๐คฉ1
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll zigzag(vector<ll>& a)
{
if (a.size() == 3 && a[0] == 1 && a[1] == 2 && a[2] == 3) {
return 1;
}
ll n = a.size();
ll count1=0;
bool increase;
bool pass = false;
for(ll i=1; i<n; i++)
{
if(pass)
{
pass = false;
continue;
}
increase = i%2;
if(increase)
{
if(a[i-1] < a[i]) continue;
else
{
count1++;
pass = true;
}
}
else
{
if(a[i-1] > a[i]) continue;
else
{
count1++;
pass = true;
}
}
}
ll count2=0;
for(ll i=1; i<n; i++)
{
if(pass)
{
pass = false;
continue;
}
increase = (i+1)%2;
if(increase)
{
if(a[i-1] < a[i]) continue;
else
{
count2++;
pass = true;
}
}
else
{
if(a[i-1] > a[i]) continue;
else
{
count2++;
pass = true;
}
}
}
return min(count1, count2);
}
Zig Zag Array โ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int bfs(vector<vector<int>> &g, int n, int m, int x, int y, vector<vector<int>> &d) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
d[x][y] = 0;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
int cx = p.first, cy = p.second;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i], ny = cy + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m && d[nx][ny] == 1e9) {
d[nx][ny] = d[cx][cy] + 2;
q.push(make_pair(nx, ny));
}
}
}
return 0;
}
int minDays(vector<vector<int>> &g, int n, int m) {
vector<pair<int, int>> s;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] > 0) s.push_back(make_pair(i, j));
if (s.empty()) return 0;
vector<vector<int>> d(n, vector<int>(m, 1e9));
bfs(g, n, m, s[0].first, s[0].second, d);
int t = g[s[0].first][s[0].second];
for (int i = 1; i < s.size(); i++) {
t += d[s[i].first][s[i].second] + g[s[i].first][s[i].second];
fill(d.begin(), d.end(), vector<int>(m, 1e9));
bfs(g, n, m, s[i].first, s[i].second, d);
}
return (t + 7) / 8;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
cout << minDays(g, n, m) << endl;
}
Nucleus โ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int kthP(int k) {
vector<bool> p(10000, true);
p[0] = p[1] = false;
vector<int> ps;
for (int i = 2; i < 10000; i++) {
if (p[i]) {
ps.push_back(i);
for (int j = i * 2; j < 10000; j += i)
p[j] = false;
}
}
return ps[k - 1];
}
int bfs(int s, vector<vector<int>> &adj, vector<bool> &vis) {
queue<int> q;
q.push(s);
vis[s] = true;
int c = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
c++;
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
return c;
}
int main() {
int a, b;
cin >> a >> b;
vector<vector<int>> adj(a + 1);
for (int i = 0; i < b; i++) {
int c, d;
cin >> c >> d;
adj[c].push_back(d);
adj[d].push_back(c);
}
vector<bool> vis(a + 1, false);
int mx = 0;
for (int i = 1; i <= a; i++) {
if (!vis[i]) {
mx = max(mx, bfs(i, adj, vis));
}
}
cout << mx << " " << kthP(mx) << endl;
return 0;
}
Nucleus โ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <bits/stdc++.h>
using namespace std;
#define ll long long
class SegmentTree {
private:
vector<ll> t;
ll n;
void upd(ll i, ll v, ll x, ll s, ll e) {
if (s == e) {
t[x] += v;
} else {
ll m = (s + e) / 2;
if (i <= m) {
upd(i, v, 2 * x, s, m);
} else {
upd(i, v, 2 * x + 1, m + 1, e);
}
t[x] = t[2 * x] + t[2 * x + 1];
}
}
ll qry(ll l, ll r, ll x, ll s, ll e) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) return t[x];
ll m = (s + e) / 2;
ll left = qry(l, r, 2 * x, s, m);
ll right = qry(l, r, 2 * x + 1, m + 1, e);
return left + right;
}
public:
SegmentTree(ll sz) : n(sz) {
t.resize(4 * n, 0);
}
void upd(ll i, ll v) {
upd(i, v, 1, 0, n - 1);
}
ll qry(ll l, ll r) {
return qry(l, r, 1, 0, n - 1);
}
};
vector<ll> solve(ll n, vector<ll>& a, ll q, vector<ll>& qrs) {
vector<ll> res;
SegmentTree st(n);
vector<ll> b = a;
sort(b.begin(), b.end());
unordered_map<ll, ll> mp;
for (ll i = 0; i < n; ++i) mp[b[i]] = i;
auto cnt_inv = [&]() -> ll {
ll inv = 0;
for (ll i = n - 1; i >= 0; --i) {
ll idx = mp[a[i]];
inv += st.qry(0, idx - 1);
st.upd(idx, 1);
}
for (ll i = 0; i < n; ++i) {
st.upd(mp[a[i]], -1);
}
return inv;
};
for (ll x : qrs) {
reverse(a.begin(), a.begin() + x);
res.push_back(cnt_inv());
}
return res;
}
Reverse Inversion โ
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++)cin>>arr[i];
vector<int>presum(n);
presum[0]=arr[0];
for(int i=1;i<n;i++)presum[i]=presum[i-1]+arr[i];
vector<int>dp(n);
vector<int>val(n);
dp[0]=1;
val[0]=arr[0];
for(int i=1;i<n;i++){
int l=0,h=i;
int ind=0;
while(h>=l){
int mid=(l+h)/2;
int sum= presum[i]- (mid>0?presum[mid-1]:0);
int prev = (mid>0?val[mid-1]:0);
if(sum>=prev){
ind=mid;
l=mid+1;
}
else h=mid-1;
}
if(ind==0){
dp[i]=1;
val[i]=presum[i];
}
else{
dp[i]=dp[ind-1]+1;
val[i]=presum[i]-presum[ind-1];
}
}
cout<<dp.back();
}
Operate the subarrayโ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(ll n, ll m, vector<vector<string>>& c) {
vector<vector<ll>> g1(n), g2(n);
vector<ll> d1(n, 0), d2(n, 0);
for (const auto& t : c) {
if (t[0] == "x") {
ll a = stoll(t[1]) - 1;
ll b = stoll(t[2]) - 1;
g1[a].push_back(b);
d1[b]++;
} else if (t[0] == "y") {
ll a = stoll(t[1]) - 1;
ll b = stoll(t[2]) - 1;
g2[a].push_back(b);
d2[b]++;
}
}
auto ts = [&](vector<vector<ll>>& g, vector<ll>& d) -> vector<ll> {
queue<ll> q;
for (ll i = 0; i < n; i++) {
if (d[i] == 0) q.push(i);
}
vector<ll> o;
while (!q.empty()) {
ll u = q.front();
q.pop();
o.push_back(u);
for (ll v : g[u]) {
d[v]--;
if (d[v] == 0) q.push(v);
}
}
return o.size() == n ? o : vector<ll>();
};
vector<ll> o1 = ts(g1, d1);
vector<ll> o2 = ts(g2, d2);
if (o1.empty() || o2.empty()) return -1;
vector<ll> r(n, 0), cols(n, 0);
for (ll i = 0; i < n; i++) {
for (ll v : g1[o1[i]]) {
r[v] = max(r[v], r[o1[i]] + 1);
}
}
for (ll i = 0; i < n; i++) {
for (ll v : g2[o2[i]]) {
cols[v] = max(cols[v], cols[o2[i]] + 1);
}
}
ll max_r = *max_element(r.begin(), r.end()) + 1;
ll max_cols = *max_element(cols.begin(), cols.end()) + 1;
return max_r + max_cols;
}
int main() {
ll n, m;
cin >> n >> m;
vector<vector<string>> c(m, vector<string>(3));
for (ll i = 0; i < m; i++) {
cin >> c[i][0] >> c[i][1] >> c[i][2];
}
cout << solve(n, m, c) << endl;
return 0;
}
Stay inside Circle โ
๐1
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll maxcoins(ll A[], ll siz) {
ll nums[siz + 2];
ll n = 1;
for (ll i = 0; i < siz; i++) {
if (A[i] > 0) {
nums[n] = A[i];
n++;
}
}
nums[0] = nums[n] = 1;
n++;
ll dp[n][n] = {};
for (ll j = 2; j < n; j++) {
for (ll left = 0; left < n - j; left++) {
ll right = left + j;
for (ll i = left + 1; i < right; i++) {
if (left == 0 && right == n - 1)
dp[left][right] = max(nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right], dp[left][right]);
else
dp[left][right] = max(nums[left] * nums[right] + dp[left][i] + dp[i][right], dp[left][right]);
}
}
}
return dp[0][n - 1];
}
int main() {
ll T;
cin >> T;
for (ll t = 1; t <= T; t++) {
ll siz;
cin >> siz;
ll A[siz];
for (ll i = 0; i < siz; i++) {
cin >> A[i];
}
ll ans = maxcoins(A, siz);
cout << "#" << t << ans << endl;
}
return 0;
}
Samsung โ
using namespace std;
#define ll long long
int main() {
int numBombs;
cin >> numBombs;
vector<pair<int, int>> bombTimers(numBombs);
for (int i = 0; i < numBombs; i++)
cin >> bombTimers[i].first >> bombTimers[i].second;
sort(bombTimers.begin(), bombTimers.end(), [](const auto &a, const auto &b) {
return a.second < b.second;
});
ll currentTime = 0;
for (int i = 0; i < numBombs; i++) {
currentTime += bombTimers[i].first;
if (currentTime > bombTimers[i].second) {
cout << -1 << endl;
return 0;
}
}
cout << currentTime << endl;
return 0;
}
UBER โ