1728A - Colored Balls: Revisited
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
cout << max_element(a.begin(), a.end()) - a.begin() + 1 << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> p(n);
iota(p.begin(), p.end(), 1);
for (int i = n & 1; i < n - 2; i += 2) swap(p[i], p[i + 1]);
for (int &x : p) cout << x << ' ';
cout << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
forn(i, n) scanf("%d", &a[i]);
forn(i, n) scanf("%d", &b[i]);
priority_queue<int> qa(a.begin(), a.end());
priority_queue<int> qb(b.begin(), b.end());
int ans = 0;
while (!qa.empty()){
if (qa.top() == qb.top()){
qa.pop();
qb.pop();
continue;
}
++ans;
if (qa.top() > qb.top()){
qa.push(to_string(qa.top()).size());
qa.pop();
}
else{
qb.push(to_string(qb.top()).size());
qb.pop();
}
}
printf("%d\n", ans);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int comp(char c, char d){
return c < d ? -1 : (c > d ? 1 : 0);
}
int main() {
int t;
cin >> t;
forn(_, t){
string s;
cin >> s;
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int len = 2; len <= n; len += 2) forn(l, n - len + 1){
int r = l + len;
dp[l][r] = 1;
{
int res = -1;
if (dp[l + 1][r - 1] != 0)
res = max(res, dp[l + 1][r - 1]);
else
res = max(res, comp(s[l], s[r - 1]));
if (dp[l + 2][r] != 0)
res = max(res, dp[l + 2][r]);
else
res = max(res, comp(s[l], s[l + 1]));
dp[l][r] = min(dp[l][r], res);
}
{
int res = -1;
if (dp[l + 1][r - 1] != 0)
res = max(res, dp[l + 1][r - 1]);
else
res = max(res, comp(s[r - 1], s[l]));
if (dp[l][r - 2] != 0)
res = max(res, dp[l][r - 2]);
else
res = max(res, comp(s[r - 1], s[r - 2]));
dp[l][r] = min(dp[l][r], res);
}
}
if (dp[0][n] == -1)
cout << "Alice\n";
else if (dp[0][n] == 0)
cout << "Draw\n";
else
cout << "Bob\n";
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long gcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(long long a, long long b, long long c, long long &x0, long long &y0, long long &g) {
g = gcd(abs(a), abs(b), x0, y0);
if (c % g) {
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}
int main() {
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
forn(i, n) scanf("%d%d", &a[i], &b[i]);
long long cur = accumulate(b.begin(), b.end(), 0ll);
vector<int> difs(n);
forn(i, n) difs[i] = a[i] - b[i];
sort(difs.begin(), difs.end(), greater<int>());
vector<long long> bst(n + 1);
forn(i, n + 1){
bst[i] = cur;
if (i < n)
cur += difs[i];
}
int mx = max_element(bst.begin(), bst.end()) - bst.begin();
int m;
scanf("%d", &m);
forn(_, m){
int x, y;
scanf("%d%d", &x, &y);
long long x0, y0, g;
if (!find_any_solution(x, y, n, x0, y0, g)){
puts("-1");
continue;
}
long long l = x * 1ll * y / g;
long long red = x0 * 1ll * x;
red = red + (max(0ll, mx - red) + l - 1) / l * l;
red = red - max(0ll, red - mx) / l * l;
long long ans = -1;
if (red <= n) ans = max(ans, bst[red]);
red -= l;
if (red >= 0) ans = max(ans, bst[red]);
printf("%lld\n", ans);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 1003;
int n;
int a[N];
vector<int> g[N * N];
int mt[N];
bool used[N * N];
vector<int> val;
bool kuhn(int x)
{
if(used[x]) return false;
used[x] = true;
for(auto y : g[x])
if(mt[y] == -1 || kuhn(mt[y]))
{
mt[y] = x;
return true;
}
return false;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++)
for(int j = 1; j <= n; j++)
val.push_back(a[i] * j);
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
int v = val.size();
long long ans = 0;
for(int i = 0; i < n; i++)
for(int j = 1; j <= n; j++)
{
int k = lower_bound(val.begin(), val.end(), a[i] * j) - val.begin();
g[k].push_back(i);
}
for(int i = 0; i < n; i++) mt[i] = -1;
for(int i = 0; i < v; i++)
{
if(kuhn(i))
{
ans += val[i];
for(int j = 0; j < v; j++) used[j] = false;
}
}
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main() {
int D, n, m;
scanf("%d%d%d", &D, &n, &m);
vector<int> inv(D + 1);
forn(i, D + 1) inv[i] = binpow(i, MOD - 2);
vector<int> b(n);
forn(i, n) scanf("%d", &b[i]);
vector<int> a(m);
forn(i, m) scanf("%d", &a[i]);
sort(a.begin(), a.end());
int fl = (1 << m) - 1;
vector<int> ways(1 << m, 1);
forn(i, m) forn(j, n){
int d = abs(b[j] - a[i]);
int mask;
if (b[j] > a[i]){
int r = lower_bound(a.begin(), a.end(), b[j] + d) - a.begin();
mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
}
else{
int l = lower_bound(a.begin(), a.end(), b[j] - d) - a.begin();
mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
}
ways[mask] = mul(ways[mask], d);
mask ^= (1 << i);
ways[mask] = mul(ways[mask], inv[d]);
}
forn(i, m) for (int mask = fl; mask >= 0; --mask) if ((mask >> i) & 1){
ways[mask ^ (1 << i)] = mul(ways[mask ^ (1 << i)], ways[mask]);
}
ways[0] = binpow(D + 1, n);
forn(mask, 1 << m){
ways[mask] = mul(ways[mask], __builtin_popcount(mask) & 1 ? MOD - 1 : 1);
}
forn(i, m) forn(mask, 1 << m) if (!((mask >> i) & 1)){
ways[mask ^ (1 << i)] = add(ways[mask ^ (1 << i)], ways[mask]);
}
int q;
scanf("%d", &q);
forn(_, q){
int x;
scanf("%d", &x);
int ans = binpow(D + 1, n + 1);
forn(i, m){
int d = abs(x - a[i]);
int mask;
if (x > a[i]){
int r = lower_bound(a.begin(), a.end(), x + d) - a.begin();
mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
}
else{
int l = lower_bound(a.begin(), a.end(), x - d) - a.begin();
mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
}
ans = add(ans, mul(add(ways[mask], -ways[mask ^ (1 << i)]), d));
}
printf("%d\n", ans);
}
return 0;
}