Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int main()
{
int cases;
scanf("%d", &cases);
while (cases--) {
int n;
scanf ("%d", &n);
vector <int> cnt(n + 1);
for (int i = 0; i < n; i++) {
int d;
scanf("%d", &d);
if (d < n) {
cnt[d]++;
} else {
cnt[n] = N;
}
}
bool good = true;
for (int i = 1; i <= n; i++) if (cnt[i] > cnt[i-1]) {
good = false;
break;
}
puts(good ? "YES" : "NO");
}
}
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
int main()
{
int t;
scanf ("%d", &t);
while (t--) {
long long n, k, g;
scanf ("%lld %lld %lld", &n, &k, &g);
long long stolen = min((g - 1) / 2 * n, k * g);
long long rest = (k * g - stolen) % g;
if (rest > 0) {
stolen -= (g - 1) / 2;
long long last = ((g - 1) / 2 + rest) % g;
if (last * 2 < g) {
stolen += last;
} else {
stolen -= g - last;
}
}
printf ("%lld\n", stolen);
}
}
1836C - k-th equality / 1835A - k-th equality
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
int power(int a, int e) {
if (e == 0) return 1;
return e == 1 ? a : a * power(a, e-1);
}
void answer(int a, int b) {
std::cout << a << " + " << b << " = " << a+b << std::endl;
}
int main() {
using ll = long long;
int t;
std::cin >> t;
while (t--) {
int a, b, c;
ll k;
std::cin >> a >> b >> c >> k;
bool good = false;
for (int i = power(10, a-1); i < power(10, a); ++i) {
int left = std::max(power(10, b-1), power(10, c-1) - i);
int right = std::min(power(10, b)-1, power(10, c) - 1 - i);
if (left > right) continue;
int have = right - left + 1;
if (k <= have) {
answer(i, left + k - 1);
good = true;
break;
}
k -= have;
}
if (!good) std::cout << "-1" << std::endl;
}
return 0;
}
1836D - Lottery / 1835B - Lottery
- Author: Arti1990
- Developer: Arti1990
- First solve: Nobody.Emissary / ecnerwala
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy() \
int _tests; \
cin >> _tests; \
FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())
#define M 1000000007
#define INF 1000000007LL
using namespace std;
long long n, m, k;
long long poz_l, poz_p;
vector<long long> v;
long long policz_ile(long long strzal)
{
while (poz_l < n && v[poz_l] < strzal)
poz_l++;
while (poz_p < n && v[poz_p] <= strzal)
poz_p++;
long long pocz = poz_p < k ? 0 : (strzal + v[poz_p - k]) / 2 + 1;
long long kon = poz_l + k - 1 >= n ? m : (v[poz_l + k - 1] + strzal - 1) / 2;
return max(0ll, kon - pocz + 1);
}
int solve()
{
cin >> n >> m >> k;
long long a;
forr(i, n)
{
cin >> a;
v.PB(a);
}
sort(v.begin(), v.end());
v.PB(m + 1);
long long res = policz_ile(0), best = 0;
forr(i, n)
{
long long pocz = i == 0 ? max(0ll, v[i] - 2) : max(v[i] - 2, v[i - 1] + 3);
long long kon = min(m, v[i] + 2);
for (long long s = pocz; s <= kon; s++)
{
long long ile = policz_ile(s);
if (ile > res)
{
res = ile;
best = s;
}
}
}
cout << res << " " << best << '\n';
return 0;
}
int main()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
1836E - Twin Clusters / 1835C - Twin Clusters
- Author: Anadi, w0nsh
- Developer: Fly_37
- First solve: GULAL_S_ZHENOY_UMNIKA / Um_nik
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int k, n;
scanf("%d", &k);
n = 2 << k;
vector <long long> input(n + 1);
vector <int> memHighBits(1 << k, -1);
vector <pair <int, int> > memLowBits(1 << k, {-1, -1});
auto addInterval = [&memLowBits, &input](int s, int e) {
const int remXor = input[e] ^ input[s - 1];
auto &[os, oe] = memLowBits[remXor];
if (os == -1) {
os = s, oe = e;
return false;
}
if (oe < s) {
printf("%d %d %d %d\n", os, oe, s, e);
} else {
printf("%d %d %d %d\n", min(s, os), max(s, os) - 1, oe + 1, e);
}
return true;
};
memHighBits[0] = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &input[i]);
input[i] ^= input[i - 1];
}
for (int i = 1; i <= n; ++i) {
if (memHighBits[input[i] >> k] != -1) {
if (addInterval(memHighBits[input[i] >> k] + 1, i)) {
break;
}
}
memHighBits[input[i] >> k] = i;
}
}
int main()
{
int cases;
scanf("%d", &cases);
while (cases--) {
solve();
}
return 0;
}
1836F - Doctor's Brown Hypothesis / 1835D - Doctor's Brown Hypothesis
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define pb push_back
#define FOR(i, n) for(int i = 0; i < n; i++)
using vi = vector<int>;
using vvi = vector<vi>;
struct SCC {
int cnt = 0;
vi vis, scc_nr;
vvi scc_list, DAG;
SCC(){}
SCC(vvi & G){
// G is 0 indexed!
int n = sz(G);
vvi G_rev(n);
vis = scc_nr = vi(n);
vi postorder;
for(int i = 0; i < n; i++)
if(!vis[i])
dfs_post(i, G, G_rev, postorder);
vis = vi(n);
while(sz(postorder)){
auto akt = postorder.back();
postorder.pop_back();
if(!vis[akt]){
DAG.emplace_back();
scc_list.emplace_back();
dfs_rev(akt, G_rev);
cnt++;
}
}
// optional
for(int i = 0; i < sz(DAG); i++){
sort(all(DAG[i]));
DAG[i].resize(unique(all(DAG[i])) - DAG[i].begin());
}
}
void dfs_post(int start, vvi & G, vvi & G_rev, vi & postorder){
vis[start] = 1;
for(auto & u : G[start]){
G_rev[u].pb(start);
if(!vis[u])
dfs_post(u, G, G_rev, postorder);
}
postorder.pb(start);
}
void dfs_rev(int start, vvi & G_rev){
vis[start] = true;
scc_list.back().pb(start);
scc_nr[start] = cnt;
for(auto & u : G_rev[start])
if(!vis[u])
dfs_rev(u, G_rev);
else if(scc_nr[u] != cnt)
DAG[scc_nr[u]].pb(cnt);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
long long n, m, k;
cin >> n >> m >> k;
vvi G(n);
set<pair<int, int>> edges;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
a--, b--;
G[a].pb(b);
edges.insert({a, b});
}
SCC scc(G);
vi coloring(n, -1);
auto try_coloring = [&](int num_col, const vi& group)
{
vi visited;
function<bool(int)> dfs = [&](int start){
visited.pb(start);
bool good_coloring = true;
for (auto & u : G[start])
{
if (scc.scc_nr[u] != scc.scc_nr[start])
{
continue;
}
if (coloring[u] == -1)
{
coloring[u] = (coloring[start] + 1) % num_col;
good_coloring &= dfs(u);
}
else
{
good_coloring &= coloring[u] == (coloring[start] + 1) % num_col;
}
if (not good_coloring)
{
break;
}
}
return good_coloring;
};
coloring[group[0]] = 0;
if (not dfs(group[0]))
{
for (auto & u : visited)
{
coloring[u] = -1;
}
return vvi();
}
else
{
vvi ret(num_col);
for (auto & u : visited)
{
ret[coloring[u]].push_back(u);
}
return ret;
}
};
long long ans = 0;
vi depths(n, -1);
for (vi& group : scc.scc_list)
{
n = sz(group);
if (n == 1 and edges.count({group[0], group[0]}) == 0)
{
continue;
}
int gcd = -1;
function<void(int)> dfs_depths = [&](int start)
{
for (auto & u : G[start])
{
if (scc.scc_nr[u] != scc.scc_nr[start])
{
continue;
}
if (depths[u] == -1)
{
depths[u] = depths[start] + 1;
dfs_depths(u);
}
else {
int diff = abs(depths[u] - (depths[start] + 1));
if (diff)
{
if (gcd == -1)
{
gcd = diff;
}
else
{
gcd = __gcd(gcd, diff);
}
}
}
}
};
depths[group[0]] = 0;
dfs_depths(group[0]);
assert(gcd != -1);
vvi by_color = try_coloring(gcd, group);
assert(sz(by_color) != 0);
if (k % gcd == 0)
{
FOR (i, gcd)
{
ans += sz(by_color[i]) + 1ll * sz(by_color[i]) * (sz(by_color[i]) - 1) / 2;
}
}
else if (k % gcd * 2 == gcd)
{
FOR (i, gcd / 2)
{
ans += 1ll * sz(by_color[i]) * sz(by_color[i + gcd / 2]);
}
}
}
cout << ans << '\n';
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_M = 1000 + 7;
constexpr int PRECISION = 9;
constexpr long long MOD = 1e9 + 7;
long long mod_inv[MAX_M];
long long DP[MAX_M][MAX_M][2][2];
long long DPprob[MAX_M][MAX_M][2][2];
bool updated[MAX_M][MAX_M][2][2];
// DP[correct][incorrect][backspace][bad suffix]
long long calc_mod_inv(long long n)
{
long long res = 1;
long long exp = MOD - 2;
while (exp)
{
if (exp & 1)
{
res = (res * n) % MOD;
}
exp >>= 1;
n = (n * n) % MOD;
}
return res;
}
void calc_DP(int digits, int needed)
{
DP[0][0][0][0] = 0;
DPprob[0][0][0][0] = 1;
struct ID
{
int x, y, z, s;
};
queue <ID> dp_queue;
dp_queue.push({0, 0, 0, 0});
while(!dp_queue.empty())
{
auto [x, y, z, s] = dp_queue.front();
dp_queue.pop();
if (updated[x][y][z][s])
{
continue;
}
updated[x][y][z][s] = true;
long long left = digits + 1 - x - y - z;
long long corr = needed - x;
long long incorr = digits - needed - y;
long long prob = DPprob[x][y][z][s];
if (corr == 0 and s == 0)
{
// done
continue;
}
// correct suffix
if (s == 0)
{
if (corr > 0)
{
// found the one correct digit (no need to delete)
long long opt_prob = (prob * mod_inv[left]) % MOD;
DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + DP[x][y][z][0] * mod_inv[left]) % MOD;
// found a needed but currently wrong digit (needs to be deleted)
if (corr > 1)
{
if (z == 0) // if backspace is not known, the suffix is bad
{
long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
dp_queue.push({x + 1, y, z, 1});
}
else // if backspace is known, the suffix can be instantly repaired
{
long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
}
}
dp_queue.push({x + 1, y, z, 0});
}
if (incorr > 0)
{
// found an incorrect digit
if (z == 0)
{
long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
dp_queue.push({x, y + 1, z, 1});
}
else // suffix can be repaired
{
long long opt_prob = ((prob * incorr % MOD) * mod_inv[left]) % MOD;
DPprob[x][y + 1][z][0] = (DPprob[x][y + 1][z][0] + opt_prob) % MOD;
DP[x][y + 1][z][0] = (DP[x][y + 1][z][0] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
dp_queue.push({x, y + 1, z, 0});
}
}
if (z == 0)
{
if (x > 0) // deleted correct digit
{
long long opt_prob = prob * mod_inv[left] % MOD;
DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + 2 * opt_prob) % MOD;
}
else // deleted nothing
{
long long opt_prob = prob * mod_inv[left] % MOD;
DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + opt_prob) % MOD;
}
dp_queue.push({x, y, 1, 0});
}
}
if (s == 1)
{
if (corr > 0)
{
// found a needed but currently wrong digit (needs to be deleted)
long long opt_prob = (prob * corr % MOD) * mod_inv[left] % MOD;
DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + (corr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
dp_queue.push({x + 1, y, z, 1});
}
if (incorr > 0)
{
// found an incorrect digit
long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
dp_queue.push({x, y + 1, z, 1});
}
if (z == 0)
{
// deleted bad suffix
long long opt_prob = prob * mod_inv[left] % MOD;
DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][1]) % MOD;
dp_queue.push({x, y, 1, 0});
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mod_inv[0] = 1;
for (int i = 1; i < MAX_M; ++i) {
mod_inv[i] = calc_mod_inv(i);
assert (mod_inv[i] * i % MOD == 1);
}
int n, m;
cin >> n >> m;
set <int> different_digits;
for (int i = 0; i < n; ++i)
{
int p;
cin >> p;
different_digits.insert(p);
}
int needed = different_digits.size();
calc_DP(m, needed);
long long result = 0;
for (int i = 0; i <= MAX_M; ++i)
{
result = (result + DP[needed][i][0][0]) % MOD;
result = (result + DP[needed][i][1][0]) % MOD;
}
cout << (result + n) % MOD << "\n";
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy() \
int _tests; \
cin >> _tests; \
FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())
using namespace std;
const int MXN = 1007;
int n, m;
vector<int> G[MXN];
bitset<MXN> bs[MXN], edge[MXN];
// MATCHING
const int MXM = 1007 * 2;
int skojX[MXM], skojY[MXM];
bool vis[MXM];
bool dfs_m(int x)
{
vis[x] = 1;
FOREACH(it, G[x])
if (!skojY[*it] || (!vis[skojY[*it]] && dfs_m(skojY[*it])))
{
skojX[x] = *it;
skojY[*it] = x;
return 1;
}
return 0;
}
bool skoj()
{
int czy = 1;
int res = 0;
while (czy)
{
czy = 0;
CLEAR(vis);
FOR(i, 1, n)
if (!vis[i] && !skojX[i] && dfs_m(i))
{
czy = 1;
res++;
}
}
return res == n;
}
// END OF MATCHING
void dfs(int nr, bitset<MXN> &visited, bitset<MXN> &to_visit)
{
visited[nr] = 1;
to_visit[nr] = 0;
to_visit = to_visit | (edge[nr] & (~visited));
for (int i = to_visit._Find_first(); i < SIZE(to_visit); i = to_visit._Find_next(i))
dfs(i, visited, to_visit);
}
int solve()
{
cin >> n >> m;
forr(i, m)
{
int a, b;
cin >> a >> b;
G[a].PB(b);
}
int rres = skoj();
if (rres)
{
FOR(i, 1, n)
{
for (auto j : G[i])
{
edge[i][skojY[j]] = 1;
}
}
unordered_map<bitset<MXN>, vector<int>> mapa;
vector<pair<int, int>> vec, res;
FOR(i, 1, n)
{
bitset<MXN> to_visit;
dfs(i, bs[i], to_visit);
mapa[bs[i]].PB(i);
}
for (auto p : mapa)
{
vector<int> l = p.ss;
vec.PB({bs[l[0]].count(), l[0]});
if (l.size() == 1)
{
res.PB({l[0], l[0]});
continue;
}
for (int i = 0; i < SIZE(l); i++)
{
res.PB({l[i], l[i]});
res.PB({l[i], l[(i + 1) % SIZE(l)]});
}
}
sort(vec.begin(), vec.end());
forr(i, SIZE(vec))
{
int nr = vec[i].ss;
bitset<MXN> b;
for (int j = i - 1; j >= 0; j--)
if (vec[j].ff < vec[i].ff)
{
int nr2 = vec[j].ss;
if (bs[nr][nr2] && !b[nr2])
{
b |= bs[nr2];
res.PB({nr, nr2});
}
}
}
cout << "YES" << '\n';
cout << res.size() << '\n';
for (auto p : res)
cout << p.ff << " " << p.ss + n << '\n';
}
else
{
CLEAR(vis);
FOR(i, 1, n)
{
if (skojX[i] == 0)
{
dfs_m(i);
break;
}
}
vector<int> v;
FOR(i, 1, n)
{
if (vis[i])
v.PB(i);
}
cout << "NO" << '\n';
cout << v.size() << '\n';
for (auto el : v)
cout << el << " ";
cout << '\n';
}
return 0;
}
int main()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}