Skip to content

Commit 9223372

Browse files
PacemakerXPacemakerX
committed
400th Question stacked
1 parent 0dd984f commit 9223372

File tree

6 files changed

+828
-0
lines changed

6 files changed

+828
-0
lines changed

‎solutions_codForces/336731659_1504_B.cpp

Lines changed: 193 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,193 @@
1+
#include <algorithm>
2+
#include <bits/stdc++.h>
3+
#include <numeric>
4+
using namespace std;
5+
6+
// Type definitions
7+
typedef long long ll;
8+
typedef pair<int, int> pii;
9+
typedef pair<ll, ll> pll;
10+
typedef vector<int> vi;
11+
typedef vector<ll> vl;
12+
typedef vector<pii> vpii;
13+
typedef vector<pll> vpll;
14+
typedef vector<vi> vvi;
15+
typedef vector<vl> vvl;
16+
17+
// Macros
18+
#define nline "\n"
19+
#define all(x) (x).begin(), (x).end()
20+
#define rall(x) (x).rbegin(), (x).rend()
21+
#define sz(x) (int)(x).size()
22+
#define pb push_back
23+
#define mp make_pair
24+
#define F first
25+
#define S second
26+
#define forn(i, n) for (int i = 0; i < int(n); i++)
27+
#define forr(i, a, b) for (int i = a; i <= b; i++)
28+
#define ford(i, a, b) for (int i = a; i >= b; i--)
29+
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
30+
31+
// clang-format off
32+
// Debug macros
33+
#define debarr(a,n) cout<<#a<<" : ";for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
34+
#define debmat(mat,row,col) cout<<#mat<<" :\n";for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}
35+
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
36+
37+
// Debug template functions
38+
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
39+
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
40+
template <class T>ostream& operator <<(ostream& os, const unordered_set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
41+
template <class S, class T>ostream& operator <<(ostream& os, const unordered_map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
42+
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
43+
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
44+
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
45+
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
46+
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
47+
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
48+
// clang-format on
49+
50+
// Constants
51+
const int MOD = 1e9 + 7;
52+
const ll INF = 1e18;
53+
const double EPS = 1e-9;
54+
const double PI = acos(-1);
55+
56+
// Utility functions
57+
ll mod_add(ll a, ll b, ll m = MOD) { return ((a % m) + (b % m)) % m; }
58+
ll mod_sub(ll a, ll b, ll m = MOD) { return ((a % m) - (b % m) + m) % m; }
59+
ll mod_mul(ll a, ll b, ll m = MOD) { return ((a % m) * (b % m)) % m; }
60+
ll mod_pow(ll base, ll exp, ll m = MOD)
61+
{
62+
ll res = 1;
63+
base %= m;
64+
while (exp > 0)
65+
{
66+
if (exp & 1)
67+
res = mod_mul(res, base, m);
68+
base = mod_mul(base, base, m);
69+
exp >>= 1;
70+
}
71+
return res;
72+
}
73+
ll mod_inv(ll a, ll m = MOD)
74+
{
75+
return mod_pow(a, m - 2, m); // Only works if m is prime
76+
}
77+
ll mod_div(ll a, ll b, ll m = MOD)
78+
{
79+
return mod_mul(a, mod_inv(b, m), m);
80+
}
81+
82+
ll binpow(ll base, ll exp, ll mod = MOD)
83+
{
84+
ll res = 1;
85+
base %= mod;
86+
while (exp > 0)
87+
{
88+
if (exp & 1)
89+
res = (res * base) % mod;
90+
base = (base * base) % mod;
91+
exp >>= 1;
92+
}
93+
return res;
94+
}
95+
/************/
96+
void solve()
97+
{
98+
int n;
99+
cin >> n;
100+
string s, t;
101+
cin >> s >> t;
102+
103+
int index = n;
104+
105+
for (int i = n - 1; i >= 0; i--)
106+
{
107+
if (s[i] != t[i])
108+
{
109+
index = i;
110+
111+
break;
112+
}
113+
}
114+
115+
if (index == n)
116+
{
117+
cout << "YES" << nline;
118+
return;
119+
}
120+
121+
int len = 0;
122+
int cnt = 1;
123+
int prev = index;
124+
int one = 0;
125+
int flagDiff = true, flagSame = false;
126+
127+
for (int i = index; i >= 0; i--)
128+
{
129+
130+
if (s[i] == t[i] && flagDiff)
131+
{
132+
cnt++;
133+
flagDiff = false;
134+
flagSame = true;
135+
136+
len = (prev - i);
137+
138+
if (len & 1 || len != (2 * one))
139+
{
140+
cout << "NO" << nline;
141+
return;
142+
}
143+
144+
one = (s[i] == '1');
145+
prev = i;
146+
}
147+
else if (s[i] != t[i] && flagSame)
148+
{
149+
cnt++;
150+
flagSame = false;
151+
flagDiff = true;
152+
153+
len = (prev - i);
154+
155+
if (len & 1 || len != (2 * one))
156+
{
157+
cout << "NO" << nline;
158+
return;
159+
}
160+
161+
one = (s[i] == '1');
162+
prev = i;
163+
}
164+
else if (s[i] == '1')
165+
one++;
166+
}
167+
168+
len = (prev + 1);
169+
if (len & 1 || len != (2 * one))
170+
cout << "NO" << nline;
171+
else
172+
cout << "YES" << nline;
173+
}
174+
int main()
175+
{
176+
177+
ios_base::sync_with_stdio(0);
178+
cin.tie(0);
179+
cout.tie(0);
180+
#ifndef ONLINE_JUDGE
181+
freopen("./outputs/input.txt", "r", stdin);
182+
freopen("./outputs/output.txt", "w", stdout);
183+
cerr.rdbuf(cout.rdbuf());
184+
#endif
185+
186+
int t;
187+
cin >> t;
188+
// int t = 1;
189+
while (t--)
190+
solve();
191+
192+
return 0;
193+
}

‎solutions_codForces/336839123_1470_A.cpp

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,156 @@
1+
#include <algorithm>
2+
#include <bits/stdc++.h>
3+
#include <numeric>
4+
using namespace std;
5+
6+
// Type definitions
7+
typedef long long ll;
8+
typedef pair<int, int> pii;
9+
typedef pair<ll, ll> pll;
10+
typedef vector<int> vi;
11+
typedef vector<ll> vl;
12+
typedef vector<pii> vpii;
13+
typedef vector<pll> vpll;
14+
typedef vector<vi> vvi;
15+
typedef vector<vl> vvl;
16+
17+
// Macros
18+
#define nline "\n"
19+
#define all(x) (x).begin(), (x).end()
20+
#define rall(x) (x).rbegin(), (x).rend()
21+
#define sz(x) (int)(x).size()
22+
#define pb push_back
23+
#define mp make_pair
24+
#define F first
25+
#define S second
26+
#define forn(i, n) for (int i = 0; i < int(n); i++)
27+
#define forr(i, a, b) for (int i = a; i <= b; i++)
28+
#define ford(i, a, b) for (int i = a; i >= b; i--)
29+
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
30+
31+
// clang-format off
32+
// Debug macros
33+
#define debarr(a,n) cout<<#a<<" : ";for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
34+
#define debmat(mat,row,col) cout<<#mat<<" :\n";for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}
35+
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
36+
37+
// Debug template functions
38+
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
39+
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
40+
template <class T>ostream& operator <<(ostream& os, const unordered_set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
41+
template <class S, class T>ostream& operator <<(ostream& os, const unordered_map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
42+
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
43+
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
44+
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
45+
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
46+
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
47+
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
48+
// clang-format on
49+
50+
// Constants
51+
const int MOD = 1e9 + 7;
52+
const ll INF = 1e18;
53+
const double EPS = 1e-9;
54+
const double PI = acos(-1);
55+
56+
// Utility functions
57+
ll mod_add(ll a, ll b, ll m = MOD) { return ((a % m) + (b % m)) % m; }
58+
ll mod_sub(ll a, ll b, ll m = MOD) { return ((a % m) - (b % m) + m) % m; }
59+
ll mod_mul(ll a, ll b, ll m = MOD) { return ((a % m) * (b % m)) % m; }
60+
ll mod_pow(ll base, ll exp, ll m = MOD)
61+
{
62+
ll res = 1;
63+
base %= m;
64+
while (exp > 0)
65+
{
66+
if (exp & 1)
67+
res = mod_mul(res, base, m);
68+
base = mod_mul(base, base, m);
69+
exp >>= 1;
70+
}
71+
return res;
72+
}
73+
ll mod_inv(ll a, ll m = MOD)
74+
{
75+
return mod_pow(a, m - 2, m); // Only works if m is prime
76+
}
77+
ll mod_div(ll a, ll b, ll m = MOD)
78+
{
79+
return mod_mul(a, mod_inv(b, m), m);
80+
}
81+
82+
ll binpow(ll base, ll exp, ll mod = MOD)
83+
{
84+
ll res = 1;
85+
base %= mod;
86+
while (exp > 0)
87+
{
88+
if (exp & 1)
89+
res = (res * base) % mod;
90+
base = (base * base) % mod;
91+
exp >>= 1;
92+
}
93+
return res;
94+
}
95+
/************/
96+
void solve()
97+
{
98+
ll n, m;
99+
cin >> n >> m;
100+
101+
vl k(n), g(m);
102+
103+
for (auto &i : k)
104+
cin >> i;
105+
106+
for (auto &i : g)
107+
cin >> i;
108+
109+
vpll arr;
110+
forn(i, n)
111+
{
112+
113+
arr.push_back({g[k[i] - 1], i});
114+
}
115+
116+
ll cost = 0LL;
117+
118+
ll idx = 0;
119+
120+
sort(rall(arr));
121+
122+
forn(i, n)
123+
{
124+
if (idx < m)
125+
{
126+
if (arr[i].first > g[idx])
127+
cost += g[idx++];
128+
else
129+
cost += arr[i].first;
130+
}
131+
else
132+
cost += arr[i].first;
133+
}
134+
135+
cout << cost << nline;
136+
}
137+
int main()
138+
{
139+
140+
ios_base::sync_with_stdio(0);
141+
cin.tie(0);
142+
cout.tie(0);
143+
#ifndef ONLINE_JUDGE
144+
freopen("./outputs/input.txt", "r", stdin);
145+
freopen("./outputs/output.txt", "w", stdout);
146+
cerr.rdbuf(cout.rdbuf());
147+
#endif
148+
149+
int t;
150+
cin >> t;
151+
// int t = 1;
152+
while (t--)
153+
solve();
154+
155+
return 0;
156+
}

0 commit comments

Comments
 (0)