Очередные Ивановские разборки. Мы надеемся, что вам понравился контест!
Идея: shishyando
Разбор
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end());
vector<int> b;
for (int i = 0; i < n; i++) {
if (i == 0 || a[i] != a[i - 1]) {
b.emplace_back(a[i]);
}
}
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] == a[i - 1]) {
b.emplace_back(a[i]);
}
}
for (auto x : b) cout << x << ' ';
cout << '\n';
}
return 0;
cout << "amogus";
}
Идея: Artyom123
Разбор
Tutorial is loading...
Реализация
//один манул
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
map<int, int> cnt;
while (n--) {
int x;
cin >> x;
cnt[x % m]++;
}
int ans = 0;
for (auto &c : cnt) {
if (c.first == 0) ans++;
else if (2 * c.first == m) {
ans++;
} else if (2 * c.first < m || cnt.find(m - c.first) == cnt.end()) {
int x = c.second, y = cnt[m - c.first];
ans += 1 + max(0, abs(x - y) - 1);
}
}
cout << ans << '\n';
}
return 0;
}
Идея: shishyando
Разбор
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n, k;
cin >> n >> k;
if (n % 2) cout << 1 << ' ' << n / 2 << ' ' << n / 2 << '\n';
else if (n % 2 == 0 && n % 4) cout << 2 << ' ' << n / 2 - 1 << ' ' << n / 2 - 1 << '\n';
else cout << n / 2 << ' ' << n / 4 << ' ' << n / 4 << '\n';
}
return 0;
}
Идея: isaf27
Разбор
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
vector<int> solve3(int n) {
if (n % 2 == 1) return {1, n / 2, n / 2};
if (n % 4 == 0) return {n / 2, n / 4, n / 4};
if (n % 2 == 0) return {2, n / 2 - 1, n / 2 - 1};
}
int main() {
int T;
cin >> T;
while (T --> 0) {
int n, k;
cin >> n >> k;
vector<int> added = solve3(n - k + 3);
for (int i = 0; i < k; ++i) {
cout << (i <3 ? added[i] : 1) << ' '; // <3
}
cout << '\n';
}
return 0;
}
Идея: shishyando
Разбор
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
vector<long long> s(n), tag(n), dp(n, 0);
for (int i = 0; i < n; ++i) cin >> tag[i];
for (int i = 0; i < n; ++i) cin >> s[i];
for (int j = 1; j < n; ++j) {
for (int i = j - 1; i >= 0; --i) {
if (tag[i] == tag[j]) continue;
long long dpi = dp[i], dpj = dp[j], p = abs(s[i] - s[j]);
dp[i] = max(dp[i], dpj + p);
dp[j] = max(dp[j], dpi + p);
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
return 0;
}
1497E1 - Square-Free Division (easy version)
Идея: Artyom123
Разбор
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
const int MAXA = 1e7;
vector<int> primes;
int mind[MAXA + 1];
int main() {
for (int i = 2; i <= MAXA; ++i) {
if (mind[i] == 0) {
primes.emplace_back(i);
mind[i] = i;
}
for (auto &x : primes) {
if (x > mind[i] || x * i > MAXA) break;
mind[x * i] = x;
}
}
int T;
cin >> T;
while (T --> 0) {
int n, k;
cin >> n >> k;
vector<int> a(n, 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
int cnt = 0, last = 0;
while (x > 1) {
int p = mind[x];
if (last == p) {
++cnt;
} else {
if (cnt % 2 == 1) a[i] *= last;
last = p;
cnt = 1;
}
x /= p;
}
if (cnt % 2 == 1) a[i] *= last;
}
int L = 0, ans = 1;
map<int, int> last;
for (int i = 0; i < n; ++i) {
if (last.find(a[i]) != last.end() && last[a[i]] >= L) {
++ans;
L = i;
}
last[a[i]] = i;
}
cout << ans << '\n';
}
return 0;
}
1497E2 - Square-Free Division (hard version)
Идея: isaf27
Разбор
Tutorial is loading...
Реализация
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ld long double
#define ll long long
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define pii pair<int, int>
const int INF = 1e9 + 1;
const ll INFLL = 1e18 + 1;
const int MAXA = 1e7;
vector<int> primes;
int mind[MAXA + 1];
int main() {
for (int i = 2; i <= MAXA; ++i) {
if (mind[i] == 0) {
primes.emplace_back(i);
mind[i] = i;
}
for (auto &x : primes) {
if (x > mind[i] || x * i > MAXA) break;
mind[x * i] = x;
}
}
vector<int> cnt(MAXA + 1);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n, 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
int cnt = 0, last = 0;
while (x > 1) {
int p = mind[x];
if (last == p) {
++cnt;
} else {
if (cnt % 2 == 1) a[i] *= last;
last = p;
cnt = 1;
}
x /= p;
}
if (cnt % 2 == 1) a[i] *= last;
}
vector<vector<int>> mnleft(n, vector<int>(k + 1));
for (int j = 0; j <= k; j++) {
int l = n, now = 0;
for (int i = n - 1; i >= 0; i--) {
while (l - 1 >= 0 && now + (cnt[a[l - 1]] > 0) <= j) {
l--;
now += (cnt[a[l]] > 0);
cnt[a[l]]++;
}
mnleft[i][j] = l;
if (cnt[a[i]] > 1) now--;
cnt[a[i]]--;
}
}
vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
for (auto &c : dp[0]) c = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (j > 0) dp[i][j] = dp[i][j - 1];
for (int lst = 0; lst <= j; lst++) {
dp[i][j] = min(dp[i][j], dp[mnleft[i - 1][lst]][j - lst] + 1);
}
}
}
int ans = INF;
for (auto &c : dp.back()) ans = min(ans, c);
cout << ans << "\n";
}
return 0;
}