Спасибо за участие в раунде! Надеемся, что задачи вам понравились!
Автор и разработчик yunetive29
2059A - Миля и два массива
Решение
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
int a[55],b[55];
void solve(){
int n;cin>>n;
set<int> sa,sb;
for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]);
for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]);
if(sa.size()+sb.size()<4){
cout<<"NO\n";
}else{
cout<<"YES\n";
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
2059B - Стоимость массива
Автор и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
k /= 2;
vector<int> a(n);
for (auto &it: a) cin >> it;
if (2 * k == n) {
for (int i = 1; i < n; i += 2) {
if (a[i] != (i + 1) / 2) {
cout << (i + 1) / 2 << '\n';
return;
}
}
cout << k + 1 << '\n';
} else {
for (int i = 1; i <= n - 2 * k + 1; i++) {
if (a[i] != 1) {
cout << "1\n";
return;
}
}
cout << "2\n";
}
}
int main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
2059C - Обслуживание клиентов
Автор и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
const int N=305;
int a[N][N],suff[N];
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++){
suff[i]=0;
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--){
if(a[i][j]!=1)break;
suff[i]++;
}
}
multiset<int> s;
for(int i=1;i<=n;i++){
s.insert(suff[i]);
}
int ans=1;
while(!s.empty()){
int cur=*s.begin();
if(cur>=ans){
ans++;
}
s.extract(cur);
}
cout<<min(ans,n)<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
2059D - Граф и граф
Автор и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define eb emplace_back
const int INF = 1e18;
void solve() {
int n, s1, s2;
cin >> n >> s1 >> s2;
s1--, s2--;
vector<vector<int>> g1(n), g2(n);
vector<bool> good(n);
set<pair<int, int>> edges;
int m1;
cin >> m1;
for (int i = 0; i < m1; i++) {
int v, u;
cin >> v >> u;
v--, u--;
if (v > u)
swap(v, u);
edges.insert({v, u});
g1[v].eb(u);
g1[u].eb(v);
}
int m2;
cin >> m2;
for (int i = 0; i < m2; i++) {
int v, u;
cin >> v >> u;
v--, u--;
if (v > u)
swap(v, u);
if (edges.find({v, u}) != edges.end())
good[v] = true, good[u] = true;
g2[v].eb(u);
g2[u].eb(v);
}
vector<vector<int>> d(n, vector<int> (n, INF));
d[s1][s2] = 0;
set<pair<int, pair<int, int>>> st;
st.insert({0, {s1, s2}});
while (!st.empty()) {
auto [v, u] = st.begin()->second;
st.erase(st.begin());
for (auto to1 : g1[v]) {
for (auto to2 : g2[u]) {
int w = abs(to1 - to2);
if (d[to1][to2] > d[v][u] + w) {
st.erase({d[to1][to2], {to1, to2}});
d[to1][to2] = d[v][u] + w;
st.insert({d[to1][to2], {to1, to2}});
}
}
}
}
int ans = INF;
for (int i = 0; i < n; i++) {
if (!good[i])
continue;
ans = min(ans, d[i][i]);
}
if (ans == INF)
ans = -1;
cout << ans << '\n';
}
signed main() {
//cout << fixed << setprecision(5);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
//cin >> G;
while (T--)
solve();
return 0;
}
2059E1 - Хватит гамать (простая версия)
Автор shfs и разработчик yunetive29
Хинт 1
Для минимизации количества операций нужно оставить как можно больше элементов в исходном массиве. Что это за элементы?
Хинт 2
Эти элементы должны формировать префикс массива элементов изначально и подпоследовательность конечного массива.
Хинт 3
Какое ещё условие нужно наложить на префикс элементов, чтобы добавлениями можно было получить конечный массив?
Решение
Tutorial is loading...
Реализация
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n * m + 1), b(n * m + 1);
vector<deque<int>> mat(n + 1, deque<int> (m));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
int ind = j + 1 + (i - 1) * m;
mat[i][j] = ind;
cin >> a[ind];
}
}
for (int i = 1; i <= n * m; i++)
cin >> b[i];
map<int, int> mp;
for (int i = 1; i <= n * m; i++)
mp[b[i]] = i;
vector<int> s(n * m + 1), pos(n * m + 1, -1);
for (int i = 1; i <= n * m; i++) {
if (mp.find(a[i]) != mp.end())
pos[i] = mp[a[i]];
else
break;
}
pos[0] = 0;
int skipped = 0, pref = 0;
bool prev = true;
for (int i = 1; i <= n * m; i++) {
if (pos[i - 1] > pos[i])
break;
int d = pos[i] - pos[i - 1] - 1;
if (prev)
skipped += d;
else if (d > 0)
break;
if (skipped >= m - 1)
prev = true;
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
prev = true;
else
prev = false;
if (prev)
pref = i;
}
cout << n * m - pref << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
2059E2 - Хватит гамать (сложная версия)
Автор shfs и разработчик yunetive29
Решение
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define int long long
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int INF = 1e9 + 1000;
struct segtree {
vector<pair<int, int>> tree;
vector<int> ass;
int size = 1;
void init(vector<int> &a) {
while (a.size() >= size) {
size <<= 1;
}
tree.assign(2 * size, {});
ass.assign(2 * size, 0);
build(0, 0, size, a);
}
void build(int x, int lx, int rx, vector<int> &a) {
if (rx - lx == 1) {
tree[x].se = lx;
if (lx < a.size()) {
tree[x].fi = a[lx];
} else {
tree[x].fi = INF;
}
return;
}
int m = (lx + rx) / 2;
build(2 * x + 1, lx, m, a);
build(2 * x + 2, m, rx, a);
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
}
void push(int x, int lx, int rx) {
tree[x].fi += ass[x];
if (rx - lx == 1) {
ass[x] = 0;
return;
}
ass[2 * x + 1] += ass[x];
ass[2 * x + 2] += ass[x];
ass[x] = 0;
}
void update(int l, int r, int val, int x, int lx, int rx) {
push(x, lx, rx);
if (l <= lx && rx <= r) {
ass[x] += val;
push(x, lx, rx);
return;
}
if (rx <= l || r <= lx) {
return;
}
int m = (lx + rx) / 2;
update(l, r, val, 2 * x + 1, lx, m);
update(l, r, val, 2 * x + 2, m, rx);
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
}
void update(int l, int r, int val) {
update(l, r + 1, val, 0, 0, size);
}
int req(int x, int lx, int rx) {
push(x, lx, rx);
if (rx - lx == 1) {
return tree[x].se;
}
int m = (lx + rx) / 2;
push(2 * x + 1, lx, m);
push(2 * x + 2, m, rx);
if (tree[2 * x + 2].fi == 0) {
return req(2 * x + 2, m, rx);
} else {
return req(2 * x + 1, lx, m);
}
}
int req() {
return req(0, 0, size);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n * m + 1), b(n * m + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
int ind = j + 1 + (i - 1) * m;
cin >> a[ind];
}
}
for (int i = 1; i <= n * m; i++)
cin >> b[i];
map<int, int> mp;
for (int i = 1; i <= n * m; i++)
mp[b[i]] = i;
vector<int> s(n * m + 1), pos(n * m + 1, -1);
for (int i = 1; i <= n * m; i++) {
if (mp.find(a[i]) != mp.end())
pos[i] = mp[a[i]];
else
break;
}
pos[0] = 0;
int skipped = 0, pref = 0;
bool prev = true;
for (int i = 1; i <= n * m; i++) {
if (pos[i - 1] > pos[i])
break;
int d = pos[i] - pos[i - 1] - 1;
if (prev)
skipped += d;
else if (d > 0)
break;
if (skipped >= m - 1)
prev = true;
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
prev = true;
else
prev = false;
if (prev)
pref = i;
}
for (int i = 1; i <= pref; i++) {
s[i - 1] = pos[i] - pos[i - 1] - 1;
}
s[pref] = n * m - pos[pref];
vector<pair<int, int>> ans;
int res = 0;
for (int i = 0; i <= n * m; i++) {
res += s[i];
}
vector<int> ost(pref + 1);
for (int i = 1; i <= pref; i++) {
ost[i] = (m - i % m) % m;
}
for (int i = 0; i <= pref; i++) {
if (s[i] == 0) {
ost[i] = INF;
}
}
vector<int> gol(pref + 1);
gol[0] = 1;
for (int i = 1; i <= pref; i++) {
gol[i] = (i + m - 1) / m + 1;
}
segtree tree;
tree.init(ost);
for (int step = 0; step < res; step++) {
int chel = tree.req();
ans.eb(gol[chel], b[pos[chel] + s[chel]]);
tree.update(chel + 1, pref, -1);
s[chel]--;
if (s[chel] == 0) {
tree.update(chel, chel, INF);
}
}
cout << ans.size() << '\n';
for (auto [i, col] : ans) {
cout << i << " " << col << '\n';
}
}
signed main() {
//cout << fixed << setprecision(5);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
//cin >> G;
while (T--)
solve();
return 0;
}
