Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 9223372

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

File tree

6 files changed

+828
-0
lines changed

6 files changed

+828
-0
lines changed
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+
}
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)

AltStyle によって変換されたページ (->オリジナル) /