1335A - Candies and Two Sisters
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;
cout << (n - 1) / 2 << endl;
}
return 0;
}
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, a, b;
cin >> n >> a >> b;
for (int i = 0; i < n; ++i) {
cout << char('a' + i % b);
}
cout << endl;
}
return 0;
}
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<int> cnt(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
}
int mx = *max_element(cnt.begin(), cnt.end());
int diff = n + 1 - count(cnt.begin(), cnt.end(), 0);
cout << max(min(mx - 1, diff), min(mx, diff - 1)) << endl;
}
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--) {
for (int i = 0; i < 9; ++i) {
string s;
cin >> s;
for (auto &c : s) if (c == '2') c = '1';
cout << s << endl;
}
}
return 0;
}
1335E1 - Three Blocks Palindrome (easy version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
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<int> a(n);
for (auto &it : a) cin >> it;
vector<vector<int>> cnt(26, vector<int>(n + 1));
forn(i, n) {
forn(j, 26) cnt[j][i + 1] = cnt[j][i];
++cnt[a[i] - 1][i + 1];
}
int ans = 0;
forn(i, 26) ans = max(ans, cnt[i][n - 1]);
forn(l, n) fore(r, l, n) {
int cntin = 0, cntout = 0;
forn(el, 26) {
cntin = max(cntin, cnt[el][r + 1] - cnt[el][l]);
cntout = max(cntout, min(cnt[el][l], cnt[el][n] - cnt[el][r + 1]) * 2);
}
ans = max(ans, cntin + cntout);
}
cout << ans << endl;
}
return 0;
}
1335E2 - Three Blocks Palindrome (hard version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
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<int> a(n);
for (auto &it : a) cin >> it;
vector<vector<int>> cnt(200, vector<int>(n + 1));
vector<vector<int>> pos(200);
forn(i, n) {
forn(j, 200) cnt[j][i + 1] = cnt[j][i];
++cnt[a[i] - 1][i + 1];
pos[a[i] - 1].push_back(i);
}
int ans = 0;
forn(i, 200) {
ans = max(ans, sz(pos[i]));
forn(p, sz(pos[i]) / 2) {
int l = pos[i][p] + 1, r = pos[i][sz(pos[i]) - p - 1] - 1;
forn(el, 200) {
int sum = cnt[el][r + 1] - cnt[el][l];
ans = max(ans, (p + 1) * 2 + sum);
}
}
}
cout << ans << endl;
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int n, m, lognm;
vector<string> c, s;
vector<vector<int>> used, nxt;
void getnext(int x, int y, int &nx, int &ny) {
if (s[x][y] == 'U') nx = x - 1, ny = y;
if (s[x][y] == 'R') nx = x, ny = y + 1;
if (s[x][y] == 'D') nx = x + 1, ny = y;
if (s[x][y] == 'L') nx = x, ny = y - 1;
}
void dfs(int x, int y) {
used[x][y] = 1;
int nx = -1, ny = -1;
getnext(x, y, nx, ny);
assert(0 <= nx && nx < n && 0 <= ny && ny < m);
int v = x * m + y, to = nx * m + ny;
if (!used[nx][ny]) dfs(nx, ny);
nxt[v][0] = to;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
cin >> n >> m;
lognm = 0;
int nm = n * m;
while ((1 << lognm) <= nm) ++lognm;
c = s = vector<string>(n);
for (auto &it : c) cin >> it;
for (auto &it : s) cin >> it;
used = vector<vector<int>>(n, vector<int>(m));
nxt = vector<vector<int>>(n * m, vector<int>(lognm));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) dfs(i, j);
}
}
for (int deg = 1; deg < lognm; ++deg) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int id = i * m + j;
nxt[id][deg] = nxt[nxt[id][deg - 1]][deg - 1];
}
}
}
vector<vector<int>> black, white;
black = white = vector<vector<int>>(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int v = i * m + j, to = v;
for (int deg = lognm - 1; deg >= 0; --deg) {
if ((nm >> deg) & 1) to = nxt[to][deg];
}
if (c[i][j] == '0') ++black[to / m][to % m];
else ++white[to / m][to % m];
}
}
int all = 0, good = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (black[i][j]) {
++all;
++good;
} else if (white[i][j]) {
++all;
}
}
}
cout << all << " " << good << endl;
}
return 0;
}
Solution (actually _overrated_, fastest O(nm log nm))
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>
using namespace std;
const int N = 1e6 + 7;
const int K = 24;
int f[N];
int dp[N];
int ndp[N];
int sel[N];
int fans[N];
int sans[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
sel[i * m + j] = (s[j] == '0');
}
}
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
int to = -1;
if (s[j] == 'U') to = (i - 1) * m + j;
if (s[j] == 'D') to = (i + 1) * m + j;
if (s[j] == 'L') to = i * m + (j - 1);
if (s[j] == 'R') to = i * m + (j + 1);
f[i * m + j] = to;
}
}
n *= m;
for (int i = 0; i < n; i++) {
dp[i] = f[i];
}
for (int j = 0; j < K; j++) {
for (int i = 0; i < n; i++) {
ndp[i] = dp[dp[i]];
}
for (int i = 0; i < n; i++) {
dp[i] = ndp[i];
}
}
fill(fans, fans + n, 0);
fill(sans, sans + n, 0);
for (int i = 0; i < n; i++) {
fans[dp[i]]++;
sans[dp[i]] += sel[i];
}
int fs = 0, ss = 0;
for (int i = 0; i < n; i++) {
fs += (fans[i] > 0);
ss += (sans[i] > 0);
}
cout << fs << ' ' << ss << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> q;
while (q--) {
solve();
}
}