Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int pw = 2; pw < 30; ++pw) {
int val = (1 << pw) - 1;
if (n % val == 0) {
cerr << val << endl;
cout << n / val << endl;
break;
}
}
}
return 0;
}
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
n /= 2;
if (n & 1) {
cout << "NO" << endl;
continue;
}
cout << "YES" << endl;
for (int i = 1; i <= n; ++i) {
cout << i * 2 << " ";
}
for (int i = 1; i < n; ++i) {
cout << i * 2 - 1 << " ";
}
cout << 3 * n - 1 << endl;
}
return 0;
}
1343C - Alternating Subsequence
Idea: vovuh and MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
auto sgn = [&](int x) {
if (x > 0) return 1;
else return -1;
};
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
long long sum = 0;
for (int i = 0; i < n; ++i) {
int cur = a[i];
int j = i;
while (j < n && sgn(a[i]) == sgn(a[j])) {
cur = max(cur, a[j]);
++j;
}
sum += cur;
i = j - 1;
}
cout << sum << endl;
}
return 0;
}
1343D - Constant Palindrome Sum
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<int> cnt(2 * k + 1);
for (int i = 0; i < n / 2; ++i) {
++cnt[a[i] + a[n - i - 1]];
}
vector<int> pref(2 * k + 2);
for (int i = 0; i < n / 2; ++i) {
int l1 = 1 + a[i], r1 = k + a[i];
int l2 = 1 + a[n - i - 1], r2 = k + a[n - i - 1];
assert(max(l1, l2) <= min(r1, r2));
++pref[min(l1, l2)];
--pref[max(r1, r2) + 1];
}
for (int i = 1; i <= 2 * k + 1; ++i) {
pref[i] += pref[i - 1];
}
int ans = 1e9;
for (int sum = 2; sum <= 2 * k; ++sum) {
ans = min(ans, (pref[sum] - cnt[sum]) + (n / 2 - pref[sum]) * 2);
}
cout << ans << endl;
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
vector<vector<int>> g;
void bfs(int s, vector<int> &d) {
d[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (d[to] == INF) {
d[to] = d[v] + 1;
q.push(to);
}
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, m, a, b, c;
cin >> n >> m >> a >> b >> c;
--a, --b, --c;
vector<int> p(m);
for (auto &it : p) cin >> it;
sort(p.begin(), p.end());
vector<long long> pref(m + 1);
for (int i = 0; i < m; ++i) {
pref[i + 1] = pref[i] + p[i];
}
g = vector<vector<int>>(n);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> da(n, INF), db(n, INF), dc(n, INF);
bfs(a, da);
bfs(b, db);
bfs(c, dc);
long long ans = 1e18;
for (int i = 0; i < n; ++i) {
if (da[i] + db[i] + dc[i] > m) continue;
ans = min(ans, pref[db[i]] + pref[da[i] + db[i] + dc[i]]);
}
cout << ans << endl;
}
return 0;
}
1343F - Restore the Permutation by Sorted Segments
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<set<int>> segs;
for (int i = 0; i < n - 1; ++i) {
set<int> cur;
int k;
cin >> k;
for (int j = 0; j < k; ++j) {
int x;
cin >> x;
cur.insert(x);
}
segs.push_back(cur);
}
for (int fst = 1; fst <= n; ++fst) {
vector<int> ans;
bool ok = true;
vector<set<int>> cur = segs;
for (auto &it : cur) if (it.count(fst)) it.erase(fst);
ans.push_back(fst);
for (int i = 1; i < n; ++i) {
int cnt1 = 0;
int nxt = -1;
for (auto &it : cur) if (it.size() == 1) {
++cnt1;
nxt = *it.begin();
}
if (cnt1 != 1) {
ok = false;
break;
}
for (auto &it : cur) if (it.count(nxt)) it.erase(nxt);
ans.push_back(nxt);
}
if (ok) {
set<set<int>> all(segs.begin(), segs.end());
for (int i = 1; i < n; ++i) {
set<int> seg;
seg.insert(ans[i]);
bool found = false;
for (int j = i - 1; j >= 0; --j) {
seg.insert(ans[j]);
if (all.count(seg)) {
found = true;
all.erase(seg);
break;
}
}
if (!found) ok = false;
}
}
if (ok) {
for (auto it : ans) cout << it << " ";
cout << endl;
break;
}
}
}
return 0;
}