1851A - Escalator Conversations
Idea: Vladosiya, prepared: Aris
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
void solve() {
int n,m,k,H; cin >> n >> m >> k >> H;
int ans = 0;
forn(i, n) {
int x; cin >> x;
ans += (H != x) && abs(H - x) % k == 0 && abs(H-x) <= (m-1) * k;
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
Idea: Vladosiya, prepared: myav
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
bool solve(){
int n;
cin >> n;
vector<int>a(n), b(n);
for(int i = 0; i < n; i++){
cin >> a[i];
b[i] = a[i];
}
sort(b.begin(), b.end());
for(int i = 0; i < n; i++){
if((a[i] % 2) != (b[i] % 2)) return false;
}
return true;
}
int main(){
int t;
cin >> t;
while(t--){
cout << (solve() ? "YES" : "NO") << "\n";
}
return 0;
}
Idea: Vladosiya, prepared: myav
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
bool solve(){
int n, k;
cin >> n >> k;
vector<int>c(n);
for(int i = 0; i < n; i++) cin >> c[i];
int left = 0, right = 0, i = 0, j = n - 1;
int k_left = k, k_right = k;
if (c[0] == c[n - 1]){
k_left = k / 2;
k_right = k - k_left;
}
for(; i < n && left < k_left; i++){
if(c[i] == c[0]) left++;
}
for(; j >= 0 && right < k_right; j--){
if(c[j] == c[n - 1]) right++;
}
return (i - 1) < (j + 1);
}
int main(){
int t;
cin >> t;
while(t--){
cout << (solve() ? "YES" : "NO") << "\n";
}
}
1851D - Prefix Permutation Sums
Idea: Gornak40, prepared: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
ll n;
bool isPermutation(vector<ll> a) {
for (int i = 0; i < n; ++i) {
if (a[i] <= 0 || a[i] > n) {
return false;
}
}
set<ll> s(a.begin(), a.end());
return s.size() == n;
}
vector<ll> prefSumToArray(vector<ll> p) {
vector<ll> res(n);
res[0] = p[0];
for (int i = 1; i < n; ++i) {
res[i] = p[i] - p[i - 1];
}
return res;
}
void solve() {
cin >> n;
vector<ll> a(n - 1);
for (int i = 0; i + 1 < n; ++i) {
cin >> a[i];
}
ll x = n * (n + 1) / 2;
if (a.back() != x) {
a.push_back(x);
vector<ll> b = prefSumToArray(a);
if (isPermutation(b)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
return;
}
map<ll, int> cnt;
cnt[a[0]]++;
for (int i = 1; i < n - 1; ++i) {
cnt[a[i] - a[i - 1]]++;
}
vector<int> cntGt1;
for (auto p: cnt) {
if (p.second > 1) {
cntGt1.push_back(p.first);
}
}
if (cntGt1.size() > 1) {
cout << "NO\n";
return;
}
if (cntGt1.size() == 1) {
int x1 = cntGt1[0];
if (cnt[x1] > 2) {
cout << "NO\n";
return;
}
}
vector<int> cnt0;
for (int i = 1; i <= n; ++i) {
if (cnt[i] == 0) {
cnt0.push_back(i);
}
}
if (cnt0.size() != 2) {
cout << "NO\n";
return;
}
cout << "YES\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
solve();
}
return 0;
}
Idea: Vladosiya, prepared: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> dp;
vector<bool> used;
vector<vector<int>> sl;
int get(int v){
if(used[v]){
return dp[v];
}
used[v] = true;
int s = 0;
for(int u: sl[v]){
s += get(u);
}
if(!sl[v].empty()) dp[v] = min(dp[v], s);
return dp[v];
}
void solve(int tc) {
int n, k;
cin >> n >> k;
dp.resize(n);
used.assign(n, false);
sl.assign(n, vector<int>(0));
for(int &e: dp) cin >> e;
for(int i = 0; i < k; ++i){
int e;
cin >> e;
dp[--e] = 0;
}
for(int i = 0; i < n; ++i){
int m;
cin >> m;
sl[i].resize(m);
for(int &e: sl[i]){
cin >> e;
--e;
}
}
for(int i = 0; i < n; ++i){
get(i);
}
for(int e: dp) cout << e << " ";
}
bool multi = true;
signed main() {
int t = 1;
if(multi) cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
Idea: Gornak40, prepared: Gornak40
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(arr) arr.begin(), arr.end()
using namespace std;
const int MAXN = 200200;
const int MAXK = 30;
const int MAXMEM = MAXN * MAXK;
mt19937 rng(07062006);
struct node {
node *chi[2] {nullptr};
int sz = 0, id = -1;
};
int n, k;
int arr[MAXN];
node *mem = new node[MAXMEM];
node *root, *mpos;
void add_num(node* &v, int val, int i, int id) {
if (v == nullptr) *(v = mpos++) = node();
v->sz++;
if (i == -1) {
v->id = id;
return;
}
add_num(v->chi[val >> i & 1], val, i - 1, id);
}
int down(node *v, int val, int i, int &x, int &jans) {
if (i == -1) {
jans = v->id;
return 0;
}
int b = val >> i & 1;
if (v->chi[b])
return down(v->chi[b], val, i - 1, x ^= ((1 ^ b) << i), jans) | (1 << i);
return down(v->chi[b ^ 1], val, i - 1, x ^= ((rng() & 1) << i), jans);
}
void build() {
root = nullptr;
mpos = mem;
add_num(root, *arr, k - 1, 0);
}
tuple<int, int, int> solve() {
int ians = 0, jans = 1, xans = 0;
for (int i = 1; i < n; ++i) {
int x = 0, j = -1;
int cur = down(root, arr[i], k - 1, x, j);
if (cur > ((arr[ians] ^ xans) & (arr[jans] ^ xans)))
ians = j, jans = i, xans = x;
add_num(root, arr[i], k - 1, i);
}
return {ians, jans, xans};
}
int main() {
int t; cin >> t;
while (t--) {
cin >> n >> k;
for (int i = 0; i < n; ++i)
cin >> arr[i];
build();
auto [ians, jans, xans] = solve();
cout << ++ians << ' ' << ++jans << ' ' << xans << endl;
}
}
1851G - Vlad and the Mountains
Idea: Vladosiya, prepared: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
struct dsu{
vector<int> p, lvl;
dsu(int n){
p.resize(n);
lvl.assign(n, 0);
iota(all(p), 0);
}
int get(int i){
if(i == p[i]) return i;
return p[i] = get(p[i]);
}
bool unite(int a, int b){
a = get(a);
b = get(b);
if(a == b){
return false;
}
if(lvl[a] < lvl[b])swap(a, b);
p[b] = a;
if(lvl[a] == lvl[b]){
++lvl[a];
}
return true;
}
bool reachable(int a, int b){
return get(a) == get(b);
}
};
void solve(int tc) {
int n, m;
cin >> n >> m;
vector<pair<int, int>> h(n);
for(auto &e: h) cin >> e.x;
for(int i = 0; i < n; ++i){
h[i].y = i;
}
dsu graph(n);
vector<vector<int>> sl(n);
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
--u, --v;
if(h[u].x > h[v].x) sl[u].emplace_back(v);
else sl[v].emplace_back(u);
}
int q;
cin >> q;
vector<pair<pair<int, int>, pair<int, int>>> req(q);
for(auto &e: req){
cin >> e.y.x >> e.y.y >> e.x.x;
--e.y.x, --e.y.y;
e.x.x += h[e.y.x].x;
}
for(int i = 0; i < q; ++i){
req[i].x.y = i;
}
sort(all(h));
sort(all(req));
vector<bool> ans(q);
int j = 0;
for(auto e: req){
while (j < n && h[j].x <= e.x.x) {
for(int u: sl[h[j].y]){
graph.unite(h[j].y, u);
}
++j;
}
ans[e.x.y] = graph.reachable(e.y.x, e.y.y);
}
for(bool e: ans) cout << (e? "YES": "NO") << "\n";
}
bool multi = true;
signed main() {
int t = 1;
if(multi) cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
if(i < t) cout << "\n";
}
return 0;
}