Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
bool ans[26];
void solve() {
string s;
cin >> s;
memset(ans, 0, sizeof(ans));
for (int i = 0; i < s.size(); i++) {
int j = i;
while (j + 1 < s.size() && s[j + 1] == s[i])
j++;
if ((j - i) % 2 == 0)
ans[s[i] - 'a'] = true;
i = j;
}
for (int i = 0; i < 26; i++) if (ans[i])
cout << char('a' + i);
cout << endl;
}
int main() {
int q;
cin >> q;
while (q--) solve();
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
val q = readLine()!!.toInt()
for (ct in 1..q) {
val n = readLine()!!.toInt()
var (odd, evenGood, evenBad) = listOf(0, 0, 0)
for (i in 1..n) {
val s = readLine()!!
when {
s.length % 2 == 1 -> odd++
s.count { it == '0' } % 2 == 0 -> evenGood++
else -> evenBad++
}
}
println(n - if (odd == 0 && evenBad % 2 == 1) 1 else 0)
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
int t;
string a;
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> a;
string s[2];
for(auto x : a)
s[int(x - '0') & 1] += x;
reverse(s[0].begin(), s[0].end());
reverse(s[1].begin(), s[1].end());
string res = "";
while(!(s[0].empty() && s[1].empty())){
if(s[0].empty()){
res += s[1].back();
s[1].pop_back();
continue;
}
if(s[1].empty()){
res += s[0].back();
s[0].pop_back();
continue;
}
if(s[0].back() < s[1].back()){
res += s[0].back();
s[0].pop_back();
}
else{
res += s[1].back();
s[1].pop_back();
}
}
cout << res << endl;
}
return 0;
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 99;
const int INF = int(1e9) + 100;
int t;
int n;
long long s;
pair<int, int> p[N];
bool ok(int mid){
long long sum = 0;
int cnt = 0;
vector <int> v;
for(int i = 0; i < n; ++i){
if(p[i].second < mid)
sum += p[i].first;
else if(p[i].first >= mid){
sum += p[i].first;
++cnt;
}
else
v.push_back(p[i].first);
}
assert(is_sorted(v.begin(), v.end()));
int need = max(0, (n + 1) / 2 - cnt);
if(need > v.size()) return false;
for(int i = 0; i < v.size(); ++i){
if(i < v.size() - need)
sum += v[i];
else
sum += mid;
}
return sum <= s;
}
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d %lld", &n, &s);
for(int i = 0; i < n; ++i)
scanf("%d %d", &p[i].first, &p[i].second);
sort(p, p + n);
int lf = 1, rg = INF; ///WA -> 10^9
while(rg - lf > 1){
int mid = (lf + rg) / 2;
if(ok(mid)) lf = mid;
else rg = mid;
}
printf("%d\n", lf);
}
return 0;
}
1251E1 - Voting (Easy Version)
1251E2 - Voting (Hard Version)
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int t, n;
vector <int> v[N];
int main() {
int t;
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i)
v[i].clear();
for(int i = 0; i < n; ++i){
int x, s;
scanf("%d %d", &x, &s);
v[x].push_back(s);
}
multiset <int > q;
long long res = 0;
int pref = n;
int cnt = 0;
for(int i = n - 1; i >= 0; --i){
pref -= v[i].size();
int need = i - pref;
for(auto x : v[i]) q.insert(x);
while(cnt < need){
++cnt;
res += *q.begin();
q.erase(q.begin());
}
}
printf("%lld\n", res);
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int LOGN = 20;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;
#define forn(i, n) for(int i = 0; i < int(n); i++)
inline int mul(int a, int b)
{
return (a * 1ll * b) % MOD;
}
inline int norm(int a)
{
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
inline int binPow(int a, int k)
{
int ans = 1;
while(k > 0)
{
if(k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
inline int inv(int a)
{
return binPow(a, MOD - 2);
}
vector<int> w[LOGN];
vector<int> iw[LOGN];
vector<int> rv[LOGN];
void precalc()
{
int wb = binPow(g, (MOD - 1) / (1 << LOGN));
for(int st = 0; st < LOGN; st++)
{
w[st].assign(1 << st, 1);
iw[st].assign(1 << st, 1);
int bw = binPow(wb, 1 << (LOGN - st - 1));
int ibw = inv(bw);
int cw = 1;
int icw = 1;
for(int k = 0; k < (1 << st); k++)
{
w[st][k] = cw;
iw[st][k] = icw;
cw = mul(cw, bw);
icw = mul(icw, ibw);
}
rv[st].assign(1 << st, 0);
if(st == 0)
{
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
for(int k = 0; k < (1 << st); k++)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
inline void fft(int a[N], int n, int ln, bool inverse)
{
for(int i = 0; i < n; i++)
{
int ni = rv[ln][i];
if(i < ni)
swap(a[i], a[ni]);
}
for(int st = 0; (1 << st) < n; st++)
{
int len = (1 << st);
for(int k = 0; k < n; k += (len << 1))
{
for(int pos = k; pos < k + len; pos++)
{
int l = a[pos];
int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
a[pos] = norm(l + r);
a[pos + len] = norm(l - r);
}
}
}
if(inverse)
{
int in = inv(n);
for(int i = 0; i < n; i++)
a[i] = mul(a[i], in);
}
}
int aa[N], bb[N], cc[N];
inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc)
{
int n = 1, ln = 0;
while(n < (sza + szb))
n <<= 1, ln++;
for(int i = 0; i < n; i++)
aa[i] = (i < sza ? a[i] : 0);
for(int i = 0; i < n; i++)
bb[i] = (i < szb ? b[i] : 0);
fft(aa, n, ln, false);
fft(bb, n, ln, false);
for(int i = 0; i < n; i++)
cc[i] = mul(aa[i], bb[i]);
fft(cc, n, ln, true);
szc = n;
for(int i = 0; i < n; i++)
c[i] = cc[i];
}
vector<int> T[N];
int a[N];
int b[N];
int n, k;
int ans[N];
int Q[N];
int fact[N];
int rfact[N];
int auxa[N];
int auxb[N];
int auxc[N];
int C(int n, int k)
{
if(n < 0 || k < 0 || k > n) return 0;
return mul(fact[n], mul(rfact[k], rfact[n - k]));
}
vector<int> newtonExp(int a, int b, int p)
{
vector<int> res(p + 1);
for(int i = 0; i <= p; i++)
res[i] = mul(C(p, i), mul(binPow(a, i), binPow(b, p - i)));
return res;
}
int main()
{
precalc();
fact[0] = 1;
for(int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i);
for(int i = 0; i < N; i++) rfact[i] = inv(fact[i]);
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < k; i++) scanf("%d", &b[i]);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++) scanf("%d", &Q[i]);
map<int, int> cnt;
for(int i = 0; i < n; i++)
cnt[a[i]]++;
for(int i = 0; i < k; i++)
{
int redL = b[i];
int cnt1 = 0;
int cnt2 = 0;
for(auto x : cnt)
{
if(x.first >= redL)
break;
if(x.second == 1)
cnt1++;
else
cnt2++;
}
memset(auxa, 0, sizeof auxa);
memset(auxb, 0, sizeof auxb);
memset(auxc, 0, sizeof auxc);
vector<int> p1 = newtonExp(2, 1, cnt1);
vector<int> p2 = newtonExp(1, 1, cnt2 * 2);
int sa = p1.size();
int sb = p2.size();
int sc;
for(int j = 0; j < sa; j++)
auxa[j] = p1[j];
for(int j = 0; j < sb; j++)
auxb[j] = p2[j];
multiply(auxa, sa, auxb, sb, auxc, sc);
for(int j = 0; j < q; j++)
{
int cntW = Q[j] / 2 - redL - 1;
if(cntW >= 0 && cntW < sc)
ans[j] = norm(ans[j] + auxc[cntW]);
}
}
for(int i = 0; i < q; i++)
printf("%d\n", ans[i]);
}