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
```
```
Tutorial
Tutorial is loading...
Solution