Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
for t in range(int(input())):
n = int(input())
print(2 if n == 2 else (n & 1))
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
for t in range(int(input())):
print('NO' if len(set(input()) & set(input())) == 0 else 'YES')
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение (adedalic)
fun calc(p: IntArray, len: Int, x: Int, a: Int, y: Int, b: Int): Long {
var ans = 0L
var (cX, cY, cXY) = listOf(0, 0, 0)
for (i in 1..len) {
if (i % a == 0 && i % b == 0) cXY++
else if (i % a == 0) cX++
else if (i % b == 0) cY++
}
for (i in 0 until cXY)
ans += p[i] * (x + y)
for (i in 0 until cX)
ans += p[cXY + i] * x
for (i in 0 until cY)
ans += p[cXY + cX + i] * y;
return ans
}
fun main() {
val q = readLine()!!.toInt()
for (ct in 1..q) {
val n = readLine()!!.toInt()
val p = readLine()!!.split(' ').map { it.toInt() / 100 }
.sortedDescending().toIntArray()
var (x, a) = readLine()!!.split(' ').map { it.toInt() }
var (y, b) = readLine()!!.split(' ').map { it.toInt() }
val k = readLine()!!.toLong()
if (x < y) {
x = y.also { y = x }
a = b.also { b = a }
}
var lf = 0; var rg = n + 1
while (rg - lf > 1) {
val mid = (lf + rg) / 2
if (calc(p, mid, x, a, y, b) >= k)
rg = mid
else
lf = mid
}
if (rg > n) rg = -1
println(rg)
}
}
1223D - Сортировка последовательности
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;
int t, n;
int a[N];
int l[N], r[N];
int dp[N];
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
l[i] = INF;
r[i] = -INF;
dp[i] = 0;
}
vector <int> v;
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
--a[i];
v.push_back(a[i]);
l[a[i]] = min(l[a[i]], i);
r[a[i]] = max(r[a[i]], i);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int res = n;
for(int i = v.size() - 1; i >= 0; --i){
if(i + 1 == v.size() || r[v[i]] >= l[v[i + 1]]) dp[i] = 1;
else dp[i] = 1 + dp[i + 1];
res = min(res, int(v.size())- dp[i]);
}
printf("%d\n", res);
}
return 0;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 500 * 1000 + 13;
int n, k;
vector<pair<int, int>> g[N];
long long dp[N][2];
void calc(int v, int p = -1) {
long long cur = 0;
vector<long long> adds;
for (auto it : g[v]) {
int to = it.x;
int w = it.y;
if (to == p)
continue;
calc(to, v);
cur += dp[to][0];
adds.pb(dp[to][1] + w - dp[to][0]);
}
sort(all(adds), greater<long long>());
forn(i, min(sz(adds), k)) if (adds[i] > 0)
cur += adds[i];
dp[v][0] = dp[v][1] = cur;
if (k <= sz(adds) && adds[k - 1] > 0)
dp[v][1] -= adds[k - 1];
}
long long solve() {
scanf("%d%d", &n, &k);
forn(i, n) g[i].clear();
forn(i, n - 1) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
--x; --y;
g[x].pb(mp(y, w));
g[y].pb(mp(x, w));
}
calc(0);
return dp[0][0];
}
int main() {
int q;
scanf("%d", &q);
forn(i, q) printf("%lld\n", solve());
}
1223F - Стек-уничтожимые массивы
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int t, n;
int a[N];
int nxt[N];
int dp[N];
map<int, int> nxtX[N];
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", a + i);
for(int i = 0; i < n + 2; ++i){
nxt[i] = -1;
nxtX[i].clear();
dp[i] = 0;
}
for(int i = n - 1; i >= 0; --i){
if(nxtX[i + 1].count(a[i])){
int pos = nxtX[i + 1][a[i]];
assert(pos < n && a[pos] == a[i]);
nxt[i] = pos;
swap(nxtX[i], nxtX[pos + 1]);
if(pos < n - 1)
nxtX[i][a[pos + 1]] = pos + 1;
}
nxtX[i][a[i]] = i;
}
long long res = 0;
for(int i = n - 1; i >= 0; --i){
if(nxt[i] == -1) continue;
dp[i] = 1 + dp[nxt[i] + 1];
res += dp[i];
}
printf("%lld\n", res);
}
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore(i, 0, n)
cin >> a[i];
return true;
}
template<class A>
pair<A, A> upd(const pair<A, A> &mx, const A &val) {
return {max(mx.x, val), max(mx.y, min(mx.x, val))};
}
vector<int> cnt, sum;
vector<int> prv;
li getSum(int l, int r) {
return sum[r] - sum[l];
}
li ans, rx, ry;
void updAns(li x, li y) {
if (x < 2 || y < 2)
return;
if (ans >= x * y)
return;
ans = x * y;
rx = x, ry = y;
}
inline void solve() {
cnt.assign(*max_element(all(a)) + 1, 0);
fore(i, 0, n)
cnt[a[i]]++;
sum.assign(sz(cnt) + 1, 0);
fore(i, 0, sz(cnt))
sum[i + 1] = sum[i] + cnt[i];
prv.assign(sz(cnt), -1);
fore(i, 0, sz(prv)) {
if(i > 0)
prv[i] = prv[i - 1];
if(cnt[i] > 0)
prv[i] = i;
}
ans = 0;
fore(y, 2, sz(cnt)) {
li cntY = 0;
for(int i = 0; y * i < sz(cnt); i++)
cntY += i * 1ll * getSum(i * y, min((i + 1) * y, sz(cnt)));
pair<pt, pt> mx = {{-1, -1}, {-1, -1}};
int lf = (sz(cnt) - 1) / y * y, rg = sz(cnt);
while(lf >= 0) {
int cntMore = (mx.x.x >= 0) + (mx.y.x >= 0);
int val1 = prv[rg - 1];
if (val1 >= lf) {
mx = upd(mx, pt{val1 % y, val1});
if (cnt[val1] == 1)
val1 = prv[val1 - 1];
if (val1 >= lf)
mx = upd(mx, pt{val1 % y, val1});
}
if (mx.x.x >= 0) {
li x = (lf + mx.x.x) / 2;
li cur = cntY - lf / y;
updAns(min(cur, x), y);
}
if (mx.y.x >= 0) {
li x = lf + mx.y.x;
li cur = cntY - 2 * (lf / y);
updAns(min(cur, x), y);
if(cntMore + (mx.x.y < rg) >= 2) {
x = lf + mx.x.x;
cur--;
updAns(min(cur, x), y);
}
}
rg = lf;
lf -= y;
}
}
cout << ans << endl;
cerr << rx << " " << ry << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cerr << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение (arsijo)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 101;
const int MAX_M = 1001;
int n, m, k;
vector<pair<int, int> > v[MAX_N];
int w[MAX_N];
int a[MAX_M], b[MAX_M], c[MAX_M], color[MAX_M];
set<pair<int, int> > s[MAX_N], s2;
int deg[MAX_N][MAX_M];
inline pair<int, int> get_s2(int i){
return {s[i].begin()->first - s[i].rbegin()->first, i};
}
inline void change_edge_color(int edge, int d){
int pos1 = a[edge];
int pos2 = b[edge];
assert(s[pos1].find({deg[pos1][color[edge]], color[edge]}) != s[pos1].end());
s[pos1].erase({deg[pos1][color[edge]], color[edge]});
s[pos2].erase({deg[pos2][color[edge]], color[edge]});
deg[pos1][color[edge]] += d;
deg[pos2][color[edge]] += d;
s[pos1].insert({deg[pos1][color[edge]], color[edge]});
s[pos2].insert({deg[pos2][color[edge]], color[edge]});
}
inline void change_color(int edge, int col){
if (edge == 0 || edge > m || color[edge] == col)
return;
int pos1 = a[edge];
int pos2 = b[edge];
s2.erase(get_s2(pos1));
s2.erase(get_s2(pos2));
change_edge_color(edge, -1);
color[edge] = col;
change_edge_color(edge, 1);
s2.insert(get_s2(pos1));
s2.insert(get_s2(pos2));
}
vector<pair<int, int> > v2[MAX_N];
int deg2[MAX_N];
vector<int> vertices;
int used[MAX_N];
void dfs2(int pos){
used[pos] = 2;
for (auto e : v2[pos]){
if (used[e.first] != 2){
dfs2(e.first);
}
}
vertices.push_back(pos);
}
int _col[2];
set<int> used3;
int i;
vector<int> euler;
void dfs3(int pos, int prev = -1, int pr2 = 0){
while(!v2[pos].empty()){
int ind = v2[pos].back().second;
int to = v2[pos].back().first;
v2[pos].pop_back();
if (used3.find(ind) != used3.end()){
continue;
}
used3.insert(ind);
dfs3(to, ind, pos);
}
if (prev != -1){
euler.push_back(prev);
}
}
void stabilize_two_colors(const vector<int> &e, int col1, int col2){
assert(!e.empty());
v2[0].clear();
for (auto edge : e){
v2[a[edge]].clear();
v2[b[edge]].clear();
deg2[a[edge]] = 0;
deg2[b[edge]] = 0;
used[a[edge]] = 0;
used[b[edge]] = 0;
}
for (auto edge : e){
v2[a[edge]].push_back({b[edge], edge});
v2[b[edge]].push_back({a[edge], edge});
}
vertices.clear();
int u = m;
for (auto edge : e){
if (used[a[edge]] != 2){
int k = (int) vertices.size();
dfs2(a[edge]);
bool find = false;
for (int i = k; i < (int) vertices.size(); i++){
int v = vertices[i];
if (v2[v].size() % 2 == 1){
find = true;
++u;
v2[v].push_back({0, u});
v2[0].push_back({v, u});
}
}
if (!find){
int v = vertices[k];
for (int j = 0; j < 2; j++){
++u;
v2[v].push_back({0, u});
v2[0].push_back({v, u});
}
}
}
}
used3.clear();
euler.clear();
dfs3(0);
for (int a : euler){
change_color(a, col1);
swap(col1, col2);
}
}
void stabilize(const vector<int> &e){
s2.clear();
for (int i = 1; i <= n; i++){
s[i].clear();
for (int j = 1; j <= k; j++){
deg[i][j] = 0;
}
}
for (int edge : e){
deg[a[edge]][color[edge]]++;
deg[b[edge]][color[edge]]++;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++){
s[i].insert({deg[i][j], j});
}
s2.insert(get_s2(i));
}
while(-s2.begin()->first > 2){
int ind = s2.begin()->second;
int col1 = s[ind].begin()->second;
int col2 = s[ind].rbegin()->second;
vector<int> e2;
for (int edge : e){
if (color[edge] == col1 || color[edge] == col2){
e2.push_back(edge);
}
}
stabilize_two_colors(e2, col1, col2);
}
}
void make_random(vector<int> e){
random_shuffle(e.begin(), e.end());
for (int i = 0; i < (int) e.size(); i++){
color[e[i]] = i % k + 1;
}
stabilize(e);
}
int change[MAX_N];
void build(vector<int> e){
if ((int) e.size() <= n * k){
make_random(e);
return;
}
random_shuffle(e.begin(), e.end());
vector<int> e1, e2;
int s = (int) e.size() / 2;
for (int i = 0; i < (int) e.size(); i++){
if (i < s){
e1.push_back(e[i]);
}else{
e2.push_back(e[i]);
}
}
build(e1);
build(e2);
vector<pair<int, int> > v1(k), v2(k);
for (int i = 1; i <= k; i++){
v1[i - 1].first = v2[i - 1].first = 0;
v1[i - 1].second = v2[i - 1].second = i;
}
for (int edge : e1){
v1[color[edge] - 1].first++;
}
for (int edge : e2){
v2[color[edge] - 1].first++;
}
sort(v1.rbegin(), v1.rend());
sort(v2.begin(), v2.end());
for (int i = 0; i < k; i++){
change[v1[i].second] = i + 1;
}
for (int edge : e1){
color[edge] = change[color[edge]];
}
for (int i = 0; i < k; i++){
change[v2[i].second] = i + 1;
}
for (int edge : e2){
color[edge] = change[color[edge]];
}
stabilize(e);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(NULL));
#ifdef LOCAL
freopen("/Users/antontsypko/tsypko/input.txt", "r", stdin);
#endif
cin >> n >> m >> k;
for (int i = 1; i <= n; i++){
cin >> w[i];
}
ll sum = 0;
vector<int> e;
for (int i = 1; i <= m; i++){
cin >> a[i] >> b[i];
sum += w[a[i]] + w[b[i]];
e.push_back(i);
}
build(e);
for (int i = 1; i <= m; i++){
assert(color[i]);
cout << color[i] << endl;
}
}