Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
string s;
cin >> s;
bool ok = true;
if (s.length() % 2 == 0) {
forn(i, s.length() / 2)
if (s[i] != s[i + s.length() / 2])
ok = false;
} else
ok = false;
cout << (ok ? "YES" : "NO") << endl;
}
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
set<int> a;
for (int i = 1; i * i <= n; i++)
a.insert(i * i);
for (int i = 1; i * i * i <= n; i++)
a.insert(i * i * i);
cout << a.size() << endl;
}
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
#define len(s) (int)s.size()
using namespace std;
using ll = long long;
void solve(){
ll a, s;
cin >> a >> s;
vector<int>b;
while(s){
int x = a % 10;
int y = s % 10;
if(x <= y) b.emplace_back(y - x);
else{
s /= 10;
y += 10 * (s % 10);
if(x < y && y >= 10 && y <= 19) b.emplace_back(y - x);
else{
cout << -1 << '\n';
return;
}
}
a /= 10;
s /= 10;
}
if(a) cout << -1 << '\n';
else{
while (b.back() == 0) b.pop_back();
for(int i = len(b) - 1; i >= 0; i--) cout << b[i];
cout << '\n';
}
}
int main(){
ios_base ::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t){
solve();
t--;
}
return 0;
}
Идея: Vladosiya
Разбор
Tutorial is loading...
Решение
//
// Created by Vlad on 17.12.2021.
//
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
int n, m;
vector<vector<int>> p;
bool check(int x){
vector<bool> abl(m);
bool pair = false;
for(int i = 0; i < n; ++i){
int c = 0;
for(int j = 0; j < m; ++j){
if(p[i][j] >= x){
abl[j] = true;
c++;
}
}
if(c > 1) pair = true;
}
if(!pair && m > 1) return false;
bool ans = true;
for(bool b: abl){
ans = ans && b;
}
return ans;
}
void solve() {
cin >> n >> m;
p.assign(n, vector<int>(m));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> p[i][j];
}
}
int l = 1, r = 2;
while (check(r)) r *= 2;
while (r - l > 1){
int mid = (r + l) / 2;
if(check(mid)) l = mid;
else r = mid;
}
cout << l;
}
bool multi = true;
signed main() {
//freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
int t = 1;
if (multi) {
cin >> t;
}
for (; t != 0; --t) {
solve();
cout << "\n";
}
return 0;
}
Идея: senjougaharin
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5;
int main() {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
int n;
cin >> n;
vector<int> a(n), cnt(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[a[i]]++;
}
sort(a.begin(), a.end());
stack<int> st;
vector<ll> ans(n + 1, -1);
ll sum = 0;
for (int i = 0; i <= n; ++i) {
if (i > 0 && cnt[i - 1] == 0) {
if (st.empty()) {
break;
}
int j = st.top();
st.pop();
sum += i - j - 1;
}
ans[i] = sum + cnt[i];
while (i > 0 && cnt[i - 1] > 1) {
cnt[i - 1]--;
st.push(i - 1);
}
}
for (ll x : ans) {
cout << x << ' ';
}
cout << '\n';
}
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n, m, k;
cin >> n >> m >> k;
vector<int> p(n);
forn(i, n)
p[i] = i;
if (tt > 0)
cout << endl;
forn(round, k) {
int index = 0;
forn(table, m) {
int size = n / m;
if (table < n % m)
size++;
cout << size;
forn(j, size)
cout << " " << p[index++] + 1;
cout << endl;
}
rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end());
}
}
}
Идея: Gol_D
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int k;
map <int, vector<int>> mx;
map <int, vector<int>> my;
map <pair<int ,int>, bool> used;
map <pair<int, int>, int> time_of;
int dfs(int x, int y) {
used[{x, y}] = true;
int _min_ = time_of[{x, y}];
auto i = lower_bound(mx[x].begin(), mx[x].end(), y);
auto j = lower_bound(my[y].begin(), my[y].end(), x);
if (++i != mx[x].end() && !used[{x, *i}] && abs(*i - y) <= k) {
_min_ = min(_min_, dfs(x, *i));
}
--i;
if (i != mx[x].begin() && !used[{x, *(--i)}] && abs(*i - y) <= k) {
_min_ = min(_min_, dfs(x, *i));
}
if (++j != my[y].end() && !used[{*j, y}] && abs(*j - x) <= k) {
_min_ = min(_min_, dfs(*j, y));
}
--j;
if (j != my[y].begin() && !used[{*(--j), y}] && abs(*j - x) <= k) {
_min_ = min(_min_, dfs(*j, y));
}
return _min_;
}
void solve() {
mx.clear();
my.clear();
used.clear();
int n;
cin >> n >> k;
vector <pair<int, int>> a(n);
int x, y, timer;
for (int i = 0; i < n; ++i) {
cin >> x >> y >> timer;
a[i] = {x, y};
time_of[{x, y}] = timer;
mx[x].push_back(y);
my[y].push_back(x);
}
vector<int> res;
for (auto now: mx) {
sort(mx[now.first].begin(), mx[now.first].end());
}
for (auto now: my) {
sort(my[now.first].begin(), my[now.first].end());
}
for (auto now: a) {
if (!used[now]) {
res.push_back(dfs(now.first, now.second));
}
}
sort(res.begin(), res.end());
int ans = res.size() - 1;
for (int i = 0; i < res.size(); ++i) {
ans = min(ans, max((int)res.size() - i - 2, res[i]));
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
1619H - Permutation and Queries
Идея: Brovko
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
//#define int long long
#define ld long double
#define x first
#define y second
#define pb push_back
using namespace std;
const int Q = 100;
int n, q, p[100005], r[100005], a[100005];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 0; i < n; i++)
{
cin >> p[i];
p[i]--;
}
for(int i = 0; i < n; i++)
r[p[i]] = i;
for(int i = 0; i < n; i++)
{
int x = i;
for(int j = 0; j < Q; j++)
x = p[x];
a[i] = x;
}
while(q--)
{
int t, x, y;
cin >> t >> x >> y;
if(t == 2)
{
x--;
while(y >= Q)
{
y -= Q;
x = a[x];
}
while(y--)
x = p[x];
cout << x + 1 << "\n";
}
else
{
x--;
y--;
swap(r[p[x]], r[p[y]]);
swap(p[x], p[y]);
int ax = x;
for(int i = 0; i < Q; i++)
ax = p[ax];
int x2 = x;
for(int i = 0; i < Q; i++)
{
a[x] = ax;
x = r[x];
ax = r[ax];
}
swap(x, y);
ax = x;
for(int i = 0; i < Q; i++)
ax = p[ax];
x2 = x;
for(int i = 0; i < Q; i++)
{
a[x] = ax;
x = r[x];
ax = r[ax];
}
}
}
}