_Several unexpected Kuhn solutions passed for D1F. Could you please discuss your solutions in the comments and prove its correctness or provide any counter-examples. Author's solution uses flows with Dinic._ ↵
↵
Editorial is not completed yet. Problems D1E and D1F will be added later. Hope you enjoyed the problemset!↵
↵
Editorial was/will be written by [user:BThero,2020-09-27] and [user:BledDest,2020-09-27].↵
↵
Our tester [user:namanbansal013,2020-09-28] has made amazing video-tutorials on YouTube for problems [D2D/D1B](https://youtu.be/LS51ijnR8jI) and [D2E/D1C](https://youtu.be/rBSuG-_R3Yo). Make sure to check them out and show him some love!↵
↵
Finally added the editorial for D1E. Currently it is very complicated and error-prone. ↵
↵
Div2A by [user:BThero,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1417A]↵
</spoiler>↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)1e3 + 5;↵
↵
int n, k;↵
int arr[MAXN];↵
↵
void solve() {↵
scanf("%d %d", &n, &k);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
int mn = min_element(arr + 1, arr + n + 1) - arr;↵
int ans = 0;↵
↵
for (int i = 1; i <= n; ++i) {↵
if (i != mn) {↵
while (arr[i] + arr[mn] <= k) {↵
arr[i] += arr[mn];↵
++ans;↵
}↵
}↵
}↵
↵
printf("%d\n", ans);↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2B by [user:RedDreamer,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1417B]↵
</spoiler>↵
↵
<spoiler summary="Code in C++ (hugopm)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define len(v) ((int)((v).size()))↵
#define all(v) (v).begin(), (v).end()↵
#define rall(v) (v).rbegin(), (v).rend()↵
#define chmax(x, v) x = max((x), (v))↵
#define chmin(x, v) x = min((x), (v))↵
using namespace std;↵
using ll = long long;↵
↵
void solve() {↵
int n, tar;↵
cin >> n >> tar;↵
int curMid = 0;↵
for (int i = 0; i < n; ++i) {↵
int x; cin >> x;↵
int r;↵
if (tar % 2 == 0 && x == tar/2)↵
r = (curMid++) % 2;↵
else if (2*x < tar)↵
r = 0;↵
else↵
r = 1;↵
cout << r << " \n"[i==n-1];↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(0);↵
↵
int nbTests;↵
cin >> nbTests;↵
for (int iTest = 0; iTest < nbTests; ++iTest) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2C/Div1A by [user:RedDreamer,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)3e5 + 5;↵
↵
int f[MAXN], last[MAXN], arr[MAXN], ans[MAXN];↵
int n;↵
↵
void solve() {↵
scanf("%d", &n);↵
↵
for (int i = 1; i <= n; ++i) {↵
f[i] = last[i] = 0;↵
ans[i] = -1;↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
int x = arr[i];↵
f[x] = max(f[x], i - last[x]);↵
last[x] = i;↵
}↵
↵
for (int x = 1; x <= n; ++x) {↵
f[x] = max(f[x], n - last[x] + 1);↵
↵
for (int i = f[x]; i <= n && ans[i] == -1; ++i) {↵
ans[i] = x;↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", ans[i], " \n"[i == n]);↵
}↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2D/Div1B by [user:RedDreamer,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416B]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)1e4 + 5;↵
↵
vector<array<int, 3>> ans;↵
int arr[MAXN];↵
int n;↵
↵
void go(int x, int y, int z) {↵
arr[x] -= x * z;↵
arr[y] += x * z;↵
ans.pb({x, y, z});↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
ans.clear();↵
int sum = accumulate(arr + 1, arr + n + 1, 0);↵
↵
if (sum % n) {↵
printf("-1\n");↵
return;↵
}↵
↵
for (int i = 2; i <= n; ++i) {↵
if (arr[i] % i) {↵
go(1, i, i - arr[i] % i);↵
}↵
↵
go(i, 1, arr[i] / i);↵
}↵
↵
for (int i = 2; i <= n; ++i) {↵
go(1, i, sum / n);↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
assert(arr[i] == sum / n);↵
}↵
↵
assert((int)ans.size() <= 3 * n);↵
printf("%d\n", (int)ans.size());↵
↵
for (auto &[x, y, z] : ans) {↵
printf("%d %d %d\n", x, y, z);↵
}↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2E/Div1C by [user:DimmyT,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416C]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (RedDreamer)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define mp make_pair↵
#define pb push_back↵
#define f first↵
#define s second↵
#define ll long long↵
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)↵
#define forev(i, b, a) for(int i = (b); i >= (a); --i)↵
#define VAR(v, i) __typeof( i) v=(i)↵
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)↵
#define all(x) (x).begin(), (x).end()↵
#define sz(x) ((int)(x).size())↵
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);↵
↵
using namespace std;↵
↵
const int maxn = (int)5e6 + 100;↵
const int maxm = (int)1e6 + 100;↵
const int mod = (int)1e9 + 7;↵
const int P = (int) 1e6 + 7; ↵
const double pi = acos(-1.0);↵
↵
#define inf mod↵
↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
typedef vector<int> vi; ↵
typedef vector<ll> Vll; ↵
typedef vector<pair<int, int> > vpii;↵
typedef vector<pair<ll, ll> > vpll; ↵
↵
int n, t[2][maxn], id = 1;↵
ll dp[2][30];↵
vi g[maxn];↵
↵
void add(int x, int pos){↵
int v = 0;↵
forev(i, 29, 0){↵
int bit = ((x >> i) & 1);↵
if(!t[bit][v]) t[bit][v] = id++;↵
v = t[bit][v];↵
g[v].pb(pos); ↵
}↵
}↵
void go(int v, int b = 29){↵
int l = t[0][v], r = t[1][v];↵
if(l) go(l, b - 1);↵
if(r) go(r, b - 1);↵
if(!l || !r) return;↵
ll res = 0;↵
int ptr = 0;↵
for(auto x : g[l]){↵
while(ptr < sz(g[r]) && g[r][ptr] < x) ptr++;↵
res += ptr;↵
}↵
dp[0][b] += res;↵
dp[1][b] += sz(g[l]) * 1ll * sz(g[r]) - res;↵
}↵
void solve(){↵
scanf("%d", &n);↵
forn(i, 1, n){↵
int x;↵
scanf("%d", &x);↵
add(x, i);↵
}↵
go(0);↵
ll inv = 0;↵
int res = 0;↵
forn(i, 0, 29){↵
inv += min(dp[0][i], dp[1][i]);↵
if(dp[1][i] < dp[0][i])↵
res += (1 << i);↵
}↵
printf("%lld %d", inv, res);↵
}↵
↵
int main () {↵
int t = 1;↵
//scanf("%d", &t);↵
while(t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2F/Div1D by [user:DimmyT,2020-09-27]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416D]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)5e5 + 5;↵
const int MAXM = (int)3e5 + 5;↵
const int MAXQ = (int)5e5 + 5;↵
↵
pii e[MAXM], que[MAXQ], t[MAXN << 2];↵
vector<int> adj[MAXN];↵
int tin[MAXN], tout[MAXN], timer;↵
int par[MAXN], arr[MAXN];↵
bool del[MAXM];↵
int n, m, q;↵
↵
int getPar(int x) {↵
if (x == par[x]) {↵
return x;↵
}↵
↵
return par[x] = getPar(par[x]);↵
}↵
↵
void uni(int a, int b) {↵
a = getPar(a);↵
b = getPar(b);↵
↵
if (a == b) {↵
return;↵
}↵
↵
++n;↵
par[n] = n;↵
par[a] = n;↵
par[b] = n;↵
adj[n].pb(a);↵
adj[n].pb(b);↵
}↵
↵
void dfs(int v) {↵
tin[v] = ++timer;↵
↵
for (int to : adj[v]) {↵
dfs(to);↵
}↵
↵
tout[v] = timer;↵
}↵
↵
pii segMax(int v, int tl, int tr, int l, int r) {↵
if (l > r || tl > r || tr < l) {↵
return mp(0, 0);↵
}↵
↵
if (l <= tl && tr <= r) {↵
return t[v];↵
}↵
↵
int mid = (tl + tr) >> 1;↵
int c1 = (v << 1), c2 = (c1 | 1);↵
↵
return max(segMax(c1, tl, mid, l, r), segMax(c2, mid + 1, tr, l, r));↵
}↵
↵
void updPos(int v, int tl, int tr, int p, pii x) {↵
if (tl == tr) {↵
t[v] = x;↵
return;↵
}↵
↵
int mid = (tl + tr) >> 1;↵
int c1 = (v << 1), c2 = (c1 | 1);↵
↵
if (p <= mid) {↵
updPos(c1, tl, mid, p, x);↵
}↵
else {↵
updPos(c2, mid + 1, tr, p, x);↵
}↵
↵
t[v] = max(t[c1], t[c2]);↵
}↵
↵
void solve() {↵
scanf("%d %d %d", &n, &m, &q);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
for (int i = 1; i <= m; ++i) {↵
int u, v;↵
scanf("%d %d", &u, &v);↵
e[i] = mp(u, v);↵
}↵
↵
for (int i = 1; i <= q; ++i) {↵
int a, b;↵
scanf("%d %d", &a, &b);↵
que[i] = mp(a, b);↵
↵
if (a == 2) {↵
del[b] = 1;↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
par[i] = i;↵
}↵
↵
for (int i = 1; i <= m; ++i) {↵
if (!del[i]) {↵
uni(e[i].fi, e[i].se);↵
}↵
}↵
↵
for (int i = q; i > 0; --i) {↵
int tp = que[i].fi;↵
↵
if (tp == 2) {↵
int id = que[i].se;↵
uni(e[id].fi, e[id].se);↵
}↵
else {↵
que[i].se = getPar(que[i].se);↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
if (getPar(i) == i) {↵
dfs(i);↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
updPos(1, 1, n, tin[i], mp(arr[i], tin[i]));↵
}↵
↵
for (int i = 1; i <= q; ++i) {↵
int tp = que[i].fi;↵
↵
if (tp == 1) {↵
int v = que[i].se;↵
pii tmp = segMax(1, 1, n, tin[v], tout[v]);↵
↵
if (tmp.fi == 0) {↵
printf("0\n");↵
}↵
else {↵
printf("%d\n", tmp.fi);↵
updPos(1, 1, n, tmp.se, mp(0, 0));↵
}↵
}↵
}↵
}↵
↵
int main() {↵
int tt = 1;↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div1E by [user:BThero,2020-09-27]↵
↵
<spoiler summary="Editorial">↵
...[tutorial:1416E]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define __DBG 1↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) if (__DBG) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
↵
const int MAXN = (int)5e5 + 5;↵
↵
int arr[MAXN];↵
int n;↵
↵
void solve() {↵
scanf("%d", &n);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
int zero = 0, two = -1;↵
set<pll> one;↵
ll shifter = 0;↵
int sign = 1;↵
↵
for (int i = 1; i <= n; ++i) {↵
int x = arr[i];↵
↵
if (two != -1) {↵
zero += 2;↵
sign = 1;↵
shifter = 0;↵
one.clear();↵
↵
if (two < x) {↵
one.insert(mp(x - two, x - two));↵
}↵
}↵
else if (!one.empty()) {↵
zero++;↵
↵
if (sign == -1) {↵
// shifter - idx >= x↵
// shifter - x >= idx↵
// idx <= shifter - x↵
ll lim = shifter - x;↵
↵
while (!one.empty() && one.begin() -> se <= lim) {↵
one.erase(one.begin());↵
}↵
↵
if (!one.empty() && one.begin() -> fi <= lim) {↵
pll it = mp(lim + 1, one.begin() -> se);↵
one.erase(one.begin());↵
assert(it.fi <= it.se);↵
one.insert(it);↵
}↵
}↵
else {↵
// shifter + idx >= x↵
// idx >= x - shifter↵
ll lim = x - shifter;↵
↵
while (!one.empty() && one.rbegin() -> fi >= lim) {↵
one.erase(--one.end());↵
}↵
↵
if (!one.empty() && one.rbegin() -> se >= lim) {↵
pll it = mp(one.rbegin() -> fi, lim - 1);↵
one.erase(--one.end());↵
assert(it.fi <= it.se);↵
one.insert(it);↵
}↵
}↵
↵
shifter = x - shifter;↵
sign *= -1;↵
}↵
else {↵
sign = -1;↵
shifter = x;↵
int lim = min(arr[i - 1] - 1, x - 1);↵
↵
if (1 <= lim) {↵
one.insert(mp(1, lim));↵
}↵
}↵
↵
// consider x/2!↵
two = -1;↵
↵
if (x % 2 == 0) {↵
int y = x / 2;↵
ll val = (y - shifter) / sign;↵
auto it = one.lower_bound(mp(val + 1, (ll)-1e18));↵
bool found = 0;↵
↵
if (it != one.begin()) {↵
--it;↵
↵
if (it -> fi <= val && val <= it -> se) {↵
found = 1;↵
}↵
}↵
↵
if (found) {↵
two = y;↵
}↵
else {↵
one.insert(mp(val, val));↵
}↵
}↵
}↵
↵
int ans;↵
↵
if (two != -1) {↵
ans = zero + 2;↵
}↵
else if (!one.empty()) {↵
ans = zero + 1;↵
}↵
else {↵
ans = zero;↵
}↵
↵
printf("%d\n", 2 * n - ans);↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Alternative solution code in C++ (hugopm)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define len(v) ((int)((v).size()))↵
#define all(v) (v).begin(), (v).end()↵
#define rall(v) (v).rbegin(), (v).rend()↵
#define chmax(x, v) x = max((x), (v))↵
#define chmin(x, v) x = min((x), (v))↵
using namespace std;↵
using pii = pair<int, int>;↵
↵
struct EndSet {↵
set<int> points;↵
pii seg = {1, 0};↵
↵
int cbase = 0, cdir = 1;↵
↵
void setFree(int mx) {↵
points.clear(), cbase = 0, cdir = 1;↵
seg = {1, mx};↵
}↵
↵
void setPush(int x) {↵
setFree(0);↵
points.insert(x);↵
}↵
↵
void rotate(int balance) {↵
cbase = balance - cbase;↵
cdir = -cdir;↵
seg = {balance - seg.second, balance - seg.first};↵
}↵
↵
int tr(int x) {↵
return cbase + cdir*x;↵
}↵
↵
int anti(int x) {↵
return cdir * (x - cbase);↵
}↵
↵
bool in(int x) {↵
if (points.count(anti(x)))↵
return true;↵
return (seg.first <= x && x <= seg.second); ↵
}↵
↵
void push(int x) {↵
points.insert(anti(x));↵
}↵
↵
void popBelow(int x) {↵
seg.second = min(seg.second, x);↵
auto nextIt = [&] {↵
return (cdir == 1 ? prev(points.end()) : points.begin());↵
};↵
while (!points.empty() && tr(*nextIt()) > x)↵
points.erase(nextIt());↵
}↵
↵
bool empty() {↵
return points.empty() && seg.first > seg.second;↵
}↵
};↵
↵
void solve() {↵
int n; cin >> n;↵
EndSet util;↵
int curAns = 0;↵
for (int i = 0; i < n; ++i) {↵
int x; cin >> x;↵
util.popBelow(x-1); ↵
if (x % 2 == 0 && util.in(x/2)) {↵
curAns += 2;↵
util.setPush(x/2);↵
} else if (util.empty()) {↵
if (x % 2 == 0)↵
curAns += 1, util.setPush(x/2);↵
else↵
util.setFree(x-1);↵
} else {↵
curAns += 1;↵
if (x % 2 == 0)↵
util.push(x/2);↵
}↵
util.rotate(x);↵
} ↵
cout << 2*n - curAns << "\n";↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false), cin.tie(0);↵
int nbTests;↵
cin >> nbTests;↵
for (int iTest = 0; iTest < nbTests; ++iTest) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Div1F by [user:BThero,2020-09-27]↵
↵
<spoiler summary="Editorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
typedef vector<int> vi;↵
typedef vector<vi> vvi;↵
↵
const int dx[] = {0, 1, 0, -1};↵
const int dy[] = {1, 0, -1, 0};↵
const char dc[] = {'R', 'D', 'L', 'U'};↵
const int INF = (int)1e6;↵
const int MAXN = (int)3e5 + 5;↵
↵
namespace {↵
struct Edge {↵
int v, to, f, c;↵
↵
Edge() {↵
v = to = f = c = 0;↵
}↵
↵
Edge(int v, int to, int c) : v(v), to(to), c(c) {↵
f = 0;↵
}↵
};↵
↵
vector<Edge> e;↵
vector<int> adj[MAXN];↵
int ptr[MAXN], d[MAXN], q[MAXN];↵
int S, T, newS, newT, V;↵
int cap[2][MAXN];↵
↵
void prep() {↵
e.clear();↵
↵
for (int i = 0; i < V; ++i) {↵
adj[i].clear();↵
ptr[i] = d[i] = q[i] = 0;↵
cap[0][i] = cap[1][i] = 0;↵
}↵
}↵
↵
void addEdge(int u, int v, int c) {↵
//printf("E %d %d %d\n", u, v, c);↵
↵
adj[u].pb((int)e.size());↵
e.pb(Edge(u, v, c));↵
adj[v].pb((int)e.size());↵
e.pb(Edge(v, u, 0));↵
}↵
↵
void addEdgeLim(int u, int v) {↵
//printf("F %d %d\n", u, v);↵
++cap[0][v];↵
++cap[1][u];↵
}↵
↵
bool bfs() {↵
fill(d, d + V, -1);↵
d[newS] = 0;↵
int l = 0, r = 0;↵
q[r++] = newS;↵
↵
while (l < r) {↵
int v = q[l++];↵
↵
for (int id : adj[v]) {↵
if (e[id].f < e[id].c) {↵
int to = e[id].to;↵
↵
if (d[to] == -1) {↵
d[to] = d[v] + 1;↵
q[r++] = to;↵
}↵
}↵
}↵
}↵
↵
return d[newT] != -1;↵
}↵
↵
int dfs(int v, int flow = INF) {↵
if (!flow || v == newT) {↵
return flow;↵
}↵
↵
int sum = 0;↵
↵
for (; ptr[v] < (int)adj[v].size(); ++ptr[v]) {↵
int id = adj[v][ptr[v]];↵
int to = e[id].to;↵
int can = e[id].c - e[id].f;↵
↵
if (d[to] != d[v] + 1 || can == 0) {↵
continue;↵
}↵
↵
int pushed = dfs(to, min(flow, can));↵
↵
if (pushed > 0) {↵
e[id].f += pushed;↵
e[id ^ 1].f -= pushed;↵
sum += pushed;↵
flow -= pushed;↵
↵
if (flow == 0) {↵
return sum;↵
}↵
}↵
}↵
↵
return sum;↵
}↵
↵
int maxFlow() {↵
int ret = 0;↵
↵
while (bfs()) {↵
fill(ptr, ptr + V, 0);↵
↵
while (int pushed = dfs(newS)) {↵
ret += pushed;↵
}↵
}↵
↵
return ret;↵
}↵
}↵
↵
vvi arr, follow;↵
int n, m;↵
↵
bool inside(int x, int y) {↵
return 0 <= x && x < n && 0 <= y && y < m;↵
}↵
↵
int id(int x, int y) {↵
return x * m + y;↵
}↵
↵
void solve() {↵
scanf("%d %d", &n, &m);↵
arr = follow = vvi(n, vi(m, -1));↵
S = n * m;↵
T = S + 1;↵
newS = T + 1;↵
newT = newS + 1;↵
V = newT + 1;↵
prep();↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
scanf("%d", &arr[i][j]);↵
}↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
for (int dir = 0; dir < 4; ++dir) {↵
int ni = i + dx[dir], nj = j + dy[dir];↵
↵
if (inside(ni, nj)) {↵
if (arr[ni][nj] < arr[i][j]) {↵
follow[i][j] = dir;↵
}↵
else if ((i + j) % 2 == 0 && arr[ni][nj] == arr[i][j]) {↵
addEdge(id(i, j), id(ni, nj), 1);↵
}↵
}↵
}↵
↵
if (follow[i][j] == -1) {↵
// important vertex↵
if ((i + j) % 2) {↵
addEdgeLim(id(i, j), T);↵
}↵
else {↵
addEdgeLim(S, id(i, j));↵
}↵
}↵
else {↵
if ((i + j) % 2) {↵
addEdge(id(i, j), T, 1);↵
}↵
else {↵
addEdge(S, id(i, j), 1);↵
}↵
}↵
}↵
}↵
↵
for (int i = 0; i <= T; ++i) {↵
if (cap[0][i] > 0) {↵
addEdge(newS, i, cap[0][i]);↵
}↵
↵
if (cap[1][i] > 0) {↵
addEdge(i, newT, cap[1][i]);↵
}↵
}↵
↵
addEdge(T, S, INF);↵
maxFlow();↵
↵
for (int id : adj[newS]) {↵
if (e[id].f != e[id].c) {↵
printf("NO\n");↵
return;↵
}↵
}↵
↵
vvi ansv, ansc;↵
ansv = ansc = vvi(n, vi(m));↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
int dir = follow[i][j];↵
↵
if (dir != -1) {↵
int ni = i + dx[dir], nj = j + dy[dir];↵
ansv[i][j] = arr[i][j] - arr[ni][nj];↵
ansc[i][j] = dir;↵
}↵
}↵
}↵
↵
for (Edge it : e) {↵
int v = it.v, to = it.to;↵
↵
if (max(v, to) < n * m && it.f == it.c && it.c == 1) {↵
int ax = v / m, ay = v % m;↵
int bx = to / m, by = to % m;↵
ansv[ax][ay] = arr[ax][ay] - 1;↵
ansv[bx][by] = 1;↵
↵
for (int dir = 0; dir < 4; ++dir) {↵
if (mp(ax + dx[dir], ay + dy[dir]) == mp(bx, by)) {↵
ansc[ax][ay] = dir;↵
ansc[bx][by] = (dir + 2) % 4;↵
}↵
}↵
}↵
}↵
↵
printf("YES\n");↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
printf("%d%c", ansv[i][j], " \n"[j == m - 1]);↵
}↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
printf("%c%c", dc[ansc[i][j]], " \n"[j == m - 1]);↵
}↵
}↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
Editorial is not completed yet. Problem
↵
Editorial was/will be written by [user:BThero,2020-09-27] and [user:BledDest,2020-09-27].↵
↵
Our tester [user:namanbansal013,2020-09-28] has made amazing video-tutorials on YouTube for problems [D2D/D1B](https://youtu.be/LS51ijnR8jI) and [D2E/D1C](https://youtu.be/rBSuG-_R3Yo). Make sure to check them out and show him some love!↵
↵
Finally added the editorial for D1E. Currently it is very complicated and error-prone. ↵
↵
Div2A by [user:BThero,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1417A]↵
</spoiler>↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)1e3 + 5;↵
↵
int n, k;↵
int arr[MAXN];↵
↵
void solve() {↵
scanf("%d %d", &n, &k);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
int mn = min_element(arr + 1, arr + n + 1) - arr;↵
int ans = 0;↵
↵
for (int i = 1; i <= n; ++i) {↵
if (i != mn) {↵
while (arr[i] + arr[mn] <= k) {↵
arr[i] += arr[mn];↵
++ans;↵
}↵
}↵
}↵
↵
printf("%d\n", ans);↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2B by [user:RedDreamer,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1417B]↵
</spoiler>↵
↵
<spoiler summary="Code in C++ (hugopm)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define len(v) ((int)((v).size()))↵
#define all(v) (v).begin(), (v).end()↵
#define rall(v) (v).rbegin(), (v).rend()↵
#define chmax(x, v) x = max((x), (v))↵
#define chmin(x, v) x = min((x), (v))↵
using namespace std;↵
using ll = long long;↵
↵
void solve() {↵
int n, tar;↵
cin >> n >> tar;↵
int curMid = 0;↵
for (int i = 0; i < n; ++i) {↵
int x; cin >> x;↵
int r;↵
if (tar % 2 == 0 && x == tar/2)↵
r = (curMid++) % 2;↵
else if (2*x < tar)↵
r = 0;↵
else↵
r = 1;↵
cout << r << " \n"[i==n-1];↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(0);↵
↵
int nbTests;↵
cin >> nbTests;↵
for (int iTest = 0; iTest < nbTests; ++iTest) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2C/Div1A by [user:RedDreamer,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)3e5 + 5;↵
↵
int f[MAXN], last[MAXN], arr[MAXN], ans[MAXN];↵
int n;↵
↵
void solve() {↵
scanf("%d", &n);↵
↵
for (int i = 1; i <= n; ++i) {↵
f[i] = last[i] = 0;↵
ans[i] = -1;↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
int x = arr[i];↵
f[x] = max(f[x], i - last[x]);↵
last[x] = i;↵
}↵
↵
for (int x = 1; x <= n; ++x) {↵
f[x] = max(f[x], n - last[x] + 1);↵
↵
for (int i = f[x]; i <= n && ans[i] == -1; ++i) {↵
ans[i] = x;↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", ans[i], " \n"[i == n]);↵
}↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2D/Div1B by [user:RedDreamer,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416B]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)1e4 + 5;↵
↵
vector<array<int, 3>> ans;↵
int arr[MAXN];↵
int n;↵
↵
void go(int x, int y, int z) {↵
arr[x] -= x * z;↵
arr[y] += x * z;↵
ans.pb({x, y, z});↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
ans.clear();↵
int sum = accumulate(arr + 1, arr + n + 1, 0);↵
↵
if (sum % n) {↵
printf("-1\n");↵
return;↵
}↵
↵
for (int i = 2; i <= n; ++i) {↵
if (arr[i] % i) {↵
go(1, i, i - arr[i] % i);↵
}↵
↵
go(i, 1, arr[i] / i);↵
}↵
↵
for (int i = 2; i <= n; ++i) {↵
go(1, i, sum / n);↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
assert(arr[i] == sum / n);↵
}↵
↵
assert((int)ans.size() <= 3 * n);↵
printf("%d\n", (int)ans.size());↵
↵
for (auto &[x, y, z] : ans) {↵
printf("%d %d %d\n", x, y, z);↵
}↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2E/Div1C by [user:DimmyT,2020-09-27] ↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416C]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (RedDreamer)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define mp make_pair↵
#define pb push_back↵
#define f first↵
#define s second↵
#define ll long long↵
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)↵
#define forev(i, b, a) for(int i = (b); i >= (a); --i)↵
#define VAR(v, i) __typeof( i) v=(i)↵
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)↵
#define all(x) (x).begin(), (x).end()↵
#define sz(x) ((int)(x).size())↵
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);↵
↵
using namespace std;↵
↵
const int maxn = (int)5e6 + 100;↵
const int maxm = (int)1e6 + 100;↵
const int mod = (int)1e9 + 7;↵
const int P = (int) 1e6 + 7; ↵
const double pi = acos(-1.0);↵
↵
#define inf mod↵
↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
typedef vector<int> vi; ↵
typedef vector<ll> Vll; ↵
typedef vector<pair<int, int> > vpii;↵
typedef vector<pair<ll, ll> > vpll; ↵
↵
int n, t[2][maxn], id = 1;↵
ll dp[2][30];↵
vi g[maxn];↵
↵
void add(int x, int pos){↵
int v = 0;↵
forev(i, 29, 0){↵
int bit = ((x >> i) & 1);↵
if(!t[bit][v]) t[bit][v] = id++;↵
v = t[bit][v];↵
g[v].pb(pos); ↵
}↵
}↵
void go(int v, int b = 29){↵
int l = t[0][v], r = t[1][v];↵
if(l) go(l, b - 1);↵
if(r) go(r, b - 1);↵
if(!l || !r) return;↵
ll res = 0;↵
int ptr = 0;↵
for(auto x : g[l]){↵
while(ptr < sz(g[r]) && g[r][ptr] < x) ptr++;↵
res += ptr;↵
}↵
dp[0][b] += res;↵
dp[1][b] += sz(g[l]) * 1ll * sz(g[r]) - res;↵
}↵
void solve(){↵
scanf("%d", &n);↵
forn(i, 1, n){↵
int x;↵
scanf("%d", &x);↵
add(x, i);↵
}↵
go(0);↵
ll inv = 0;↵
int res = 0;↵
forn(i, 0, 29){↵
inv += min(dp[0][i], dp[1][i]);↵
if(dp[1][i] < dp[0][i])↵
res += (1 << i);↵
}↵
printf("%lld %d", inv, res);↵
}↵
↵
int main () {↵
int t = 1;↵
//scanf("%d", &t);↵
while(t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
Div2F/Div1D by [user:DimmyT,2020-09-27]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1416D]↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
const int MAXN = (int)5e5 + 5;↵
const int MAXM = (int)3e5 + 5;↵
const int MAXQ = (int)5e5 + 5;↵
↵
pii e[MAXM], que[MAXQ], t[MAXN << 2];↵
vector<int> adj[MAXN];↵
int tin[MAXN], tout[MAXN], timer;↵
int par[MAXN], arr[MAXN];↵
bool del[MAXM];↵
int n, m, q;↵
↵
int getPar(int x) {↵
if (x == par[x]) {↵
return x;↵
}↵
↵
return par[x] = getPar(par[x]);↵
}↵
↵
void uni(int a, int b) {↵
a = getPar(a);↵
b = getPar(b);↵
↵
if (a == b) {↵
return;↵
}↵
↵
++n;↵
par[n] = n;↵
par[a] = n;↵
par[b] = n;↵
adj[n].pb(a);↵
adj[n].pb(b);↵
}↵
↵
void dfs(int v) {↵
tin[v] = ++timer;↵
↵
for (int to : adj[v]) {↵
dfs(to);↵
}↵
↵
tout[v] = timer;↵
}↵
↵
pii segMax(int v, int tl, int tr, int l, int r) {↵
if (l > r || tl > r || tr < l) {↵
return mp(0, 0);↵
}↵
↵
if (l <= tl && tr <= r) {↵
return t[v];↵
}↵
↵
int mid = (tl + tr) >> 1;↵
int c1 = (v << 1), c2 = (c1 | 1);↵
↵
return max(segMax(c1, tl, mid, l, r), segMax(c2, mid + 1, tr, l, r));↵
}↵
↵
void updPos(int v, int tl, int tr, int p, pii x) {↵
if (tl == tr) {↵
t[v] = x;↵
return;↵
}↵
↵
int mid = (tl + tr) >> 1;↵
int c1 = (v << 1), c2 = (c1 | 1);↵
↵
if (p <= mid) {↵
updPos(c1, tl, mid, p, x);↵
}↵
else {↵
updPos(c2, mid + 1, tr, p, x);↵
}↵
↵
t[v] = max(t[c1], t[c2]);↵
}↵
↵
void solve() {↵
scanf("%d %d %d", &n, &m, &q);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
for (int i = 1; i <= m; ++i) {↵
int u, v;↵
scanf("%d %d", &u, &v);↵
e[i] = mp(u, v);↵
}↵
↵
for (int i = 1; i <= q; ++i) {↵
int a, b;↵
scanf("%d %d", &a, &b);↵
que[i] = mp(a, b);↵
↵
if (a == 2) {↵
del[b] = 1;↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
par[i] = i;↵
}↵
↵
for (int i = 1; i <= m; ++i) {↵
if (!del[i]) {↵
uni(e[i].fi, e[i].se);↵
}↵
}↵
↵
for (int i = q; i > 0; --i) {↵
int tp = que[i].fi;↵
↵
if (tp == 2) {↵
int id = que[i].se;↵
uni(e[id].fi, e[id].se);↵
}↵
else {↵
que[i].se = getPar(que[i].se);↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
if (getPar(i) == i) {↵
dfs(i);↵
}↵
}↵
↵
for (int i = 1; i <= n; ++i) {↵
updPos(1, 1, n, tin[i], mp(arr[i], tin[i]));↵
}↵
↵
for (int i = 1; i <= q; ++i) {↵
int tp = que[i].fi;↵
↵
if (tp == 1) {↵
int v = que[i].se;↵
pii tmp = segMax(1, 1, n, tin[v], tout[v]);↵
↵
if (tmp.fi == 0) {↵
printf("0\n");↵
}↵
else {↵
printf("%d\n", tmp.fi);↵
updPos(1, 1, n, tmp.se, mp(0, 0));↵
}↵
}↵
}↵
}↵
↵
int main() {↵
int tt = 1;↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
Div1E by [user:BThero,2020-09-27]↵
↵
<spoiler summary="Editorial">↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define __DBG 1↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) if (__DBG) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
↵
const int MAXN = (int)5e5 + 5;↵
↵
int arr[MAXN];↵
int n;↵
↵
void solve() {↵
scanf("%d", &n);↵
↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &arr[i]);↵
}↵
↵
int zero = 0, two = -1;↵
set<pll> one;↵
ll shifter = 0;↵
int sign = 1;↵
↵
for (int i = 1; i <= n; ++i) {↵
int x = arr[i];↵
↵
if (two != -1) {↵
zero += 2;↵
sign = 1;↵
shifter = 0;↵
one.clear();↵
↵
if (two < x) {↵
one.insert(mp(x - two, x - two));↵
}↵
}↵
else if (!one.empty()) {↵
zero++;↵
↵
if (sign == -1) {↵
// shifter - idx >= x↵
// shifter - x >= idx↵
// idx <= shifter - x↵
ll lim = shifter - x;↵
↵
while (!one.empty() && one.begin() -> se <= lim) {↵
one.erase(one.begin());↵
}↵
↵
if (!one.empty() && one.begin() -> fi <= lim) {↵
pll it = mp(lim + 1, one.begin() -> se);↵
one.erase(one.begin());↵
assert(it.fi <= it.se);↵
one.insert(it);↵
}↵
}↵
else {↵
// shifter + idx >= x↵
// idx >= x - shifter↵
ll lim = x - shifter;↵
↵
while (!one.empty() && one.rbegin() -> fi >= lim) {↵
one.erase(--one.end());↵
}↵
↵
if (!one.empty() && one.rbegin() -> se >= lim) {↵
pll it = mp(one.rbegin() -> fi, lim - 1);↵
one.erase(--one.end());↵
assert(it.fi <= it.se);↵
one.insert(it);↵
}↵
}↵
↵
shifter = x - shifter;↵
sign *= -1;↵
}↵
else {↵
sign = -1;↵
shifter = x;↵
int lim = min(arr[i - 1] - 1, x - 1);↵
↵
if (1 <= lim) {↵
one.insert(mp(1, lim));↵
}↵
}↵
↵
// consider x/2!↵
two = -1;↵
↵
if (x % 2 == 0) {↵
int y = x / 2;↵
ll val = (y - shifter) / sign;↵
auto it = one.lower_bound(mp(val + 1, (ll)-1e18));↵
bool found = 0;↵
↵
if (it != one.begin()) {↵
--it;↵
↵
if (it -> fi <= val && val <= it -> se) {↵
found = 1;↵
}↵
}↵
↵
if (found) {↵
two = y;↵
}↵
else {↵
one.insert(mp(val, val));↵
}↵
}↵
}↵
↵
int ans;↵
↵
if (two != -1) {↵
ans = zero + 2;↵
}↵
else if (!one.empty()) {↵
ans = zero + 1;↵
}↵
else {↵
ans = zero;↵
}↵
↵
printf("%d\n", 2 * n - ans);↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Alternative solution code in C++ (hugopm)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
#define len(v) ((int)((v).size()))↵
#define all(v) (v).begin(), (v).end()↵
#define rall(v) (v).rbegin(), (v).rend()↵
#define chmax(x, v) x = max((x), (v))↵
#define chmin(x, v) x = min((x), (v))↵
using namespace std;↵
using pii = pair<int, int>;↵
↵
struct EndSet {↵
set<int> points;↵
pii seg = {1, 0};↵
↵
int cbase = 0, cdir = 1;↵
↵
void setFree(int mx) {↵
points.clear(), cbase = 0, cdir = 1;↵
seg = {1, mx};↵
}↵
↵
void setPush(int x) {↵
setFree(0);↵
points.insert(x);↵
}↵
↵
void rotate(int balance) {↵
cbase = balance - cbase;↵
cdir = -cdir;↵
seg = {balance - seg.second, balance - seg.first};↵
}↵
↵
int tr(int x) {↵
return cbase + cdir*x;↵
}↵
↵
int anti(int x) {↵
return cdir * (x - cbase);↵
}↵
↵
bool in(int x) {↵
if (points.count(anti(x)))↵
return true;↵
return (seg.first <= x && x <= seg.second); ↵
}↵
↵
void push(int x) {↵
points.insert(anti(x));↵
}↵
↵
void popBelow(int x) {↵
seg.second = min(seg.second, x);↵
auto nextIt = [&] {↵
return (cdir == 1 ? prev(points.end()) : points.begin());↵
};↵
while (!points.empty() && tr(*nextIt()) > x)↵
points.erase(nextIt());↵
}↵
↵
bool empty() {↵
return points.empty() && seg.first > seg.second;↵
}↵
};↵
↵
void solve() {↵
int n; cin >> n;↵
EndSet util;↵
int curAns = 0;↵
for (int i = 0; i < n; ++i) {↵
int x; cin >> x;↵
util.popBelow(x-1); ↵
if (x % 2 == 0 && util.in(x/2)) {↵
curAns += 2;↵
util.setPush(x/2);↵
} else if (util.empty()) {↵
if (x % 2 == 0)↵
curAns += 1, util.setPush(x/2);↵
else↵
util.setFree(x-1);↵
} else {↵
curAns += 1;↵
if (x % 2 == 0)↵
util.push(x/2);↵
}↵
util.rotate(x);↵
} ↵
cout << 2*n - curAns << "\n";↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false), cin.tie(0);↵
int nbTests;↵
cin >> nbTests;↵
for (int iTest = 0; iTest < nbTests; ++iTest) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Div1F by [user:BThero,2020-09-27]↵
↵
<spoiler summary="Editorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="Code in C++ (BThero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include<bits/stdc++.h>↵
↵
#define pb push_back↵
#define eb emplace_back↵
#define mp make_pair↵
#define fi first↵
#define se second↵
#define all(x) (x).begin(), (x).end()↵
#define debug(x) cerr << #x << " = " << x << endl;↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
typedef vector<int> vi;↵
typedef vector<vi> vvi;↵
↵
const int dx[] = {0, 1, 0, -1};↵
const int dy[] = {1, 0, -1, 0};↵
const char dc[] = {'R', 'D', 'L', 'U'};↵
const int INF = (int)1e6;↵
const int MAXN = (int)3e5 + 5;↵
↵
namespace {↵
struct Edge {↵
int v, to, f, c;↵
↵
Edge() {↵
v = to = f = c = 0;↵
}↵
↵
Edge(int v, int to, int c) : v(v), to(to), c(c) {↵
f = 0;↵
}↵
};↵
↵
vector<Edge> e;↵
vector<int> adj[MAXN];↵
int ptr[MAXN], d[MAXN], q[MAXN];↵
int S, T, newS, newT, V;↵
int cap[2][MAXN];↵
↵
void prep() {↵
e.clear();↵
↵
for (int i = 0; i < V; ++i) {↵
adj[i].clear();↵
ptr[i] = d[i] = q[i] = 0;↵
cap[0][i] = cap[1][i] = 0;↵
}↵
}↵
↵
void addEdge(int u, int v, int c) {↵
//printf("E %d %d %d\n", u, v, c);↵
↵
adj[u].pb((int)e.size());↵
e.pb(Edge(u, v, c));↵
adj[v].pb((int)e.size());↵
e.pb(Edge(v, u, 0));↵
}↵
↵
void addEdgeLim(int u, int v) {↵
//printf("F %d %d\n", u, v);↵
++cap[0][v];↵
++cap[1][u];↵
}↵
↵
bool bfs() {↵
fill(d, d + V, -1);↵
d[newS] = 0;↵
int l = 0, r = 0;↵
q[r++] = newS;↵
↵
while (l < r) {↵
int v = q[l++];↵
↵
for (int id : adj[v]) {↵
if (e[id].f < e[id].c) {↵
int to = e[id].to;↵
↵
if (d[to] == -1) {↵
d[to] = d[v] + 1;↵
q[r++] = to;↵
}↵
}↵
}↵
}↵
↵
return d[newT] != -1;↵
}↵
↵
int dfs(int v, int flow = INF) {↵
if (!flow || v == newT) {↵
return flow;↵
}↵
↵
int sum = 0;↵
↵
for (; ptr[v] < (int)adj[v].size(); ++ptr[v]) {↵
int id = adj[v][ptr[v]];↵
int to = e[id].to;↵
int can = e[id].c - e[id].f;↵
↵
if (d[to] != d[v] + 1 || can == 0) {↵
continue;↵
}↵
↵
int pushed = dfs(to, min(flow, can));↵
↵
if (pushed > 0) {↵
e[id].f += pushed;↵
e[id ^ 1].f -= pushed;↵
sum += pushed;↵
flow -= pushed;↵
↵
if (flow == 0) {↵
return sum;↵
}↵
}↵
}↵
↵
return sum;↵
}↵
↵
int maxFlow() {↵
int ret = 0;↵
↵
while (bfs()) {↵
fill(ptr, ptr + V, 0);↵
↵
while (int pushed = dfs(newS)) {↵
ret += pushed;↵
}↵
}↵
↵
return ret;↵
}↵
}↵
↵
vvi arr, follow;↵
int n, m;↵
↵
bool inside(int x, int y) {↵
return 0 <= x && x < n && 0 <= y && y < m;↵
}↵
↵
int id(int x, int y) {↵
return x * m + y;↵
}↵
↵
void solve() {↵
scanf("%d %d", &n, &m);↵
arr = follow = vvi(n, vi(m, -1));↵
S = n * m;↵
T = S + 1;↵
newS = T + 1;↵
newT = newS + 1;↵
V = newT + 1;↵
prep();↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
scanf("%d", &arr[i][j]);↵
}↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
for (int dir = 0; dir < 4; ++dir) {↵
int ni = i + dx[dir], nj = j + dy[dir];↵
↵
if (inside(ni, nj)) {↵
if (arr[ni][nj] < arr[i][j]) {↵
follow[i][j] = dir;↵
}↵
else if ((i + j) % 2 == 0 && arr[ni][nj] == arr[i][j]) {↵
addEdge(id(i, j), id(ni, nj), 1);↵
}↵
}↵
}↵
↵
if (follow[i][j] == -1) {↵
// important vertex↵
if ((i + j) % 2) {↵
addEdgeLim(id(i, j), T);↵
}↵
else {↵
addEdgeLim(S, id(i, j));↵
}↵
}↵
else {↵
if ((i + j) % 2) {↵
addEdge(id(i, j), T, 1);↵
}↵
else {↵
addEdge(S, id(i, j), 1);↵
}↵
}↵
}↵
}↵
↵
for (int i = 0; i <= T; ++i) {↵
if (cap[0][i] > 0) {↵
addEdge(newS, i, cap[0][i]);↵
}↵
↵
if (cap[1][i] > 0) {↵
addEdge(i, newT, cap[1][i]);↵
}↵
}↵
↵
addEdge(T, S, INF);↵
maxFlow();↵
↵
for (int id : adj[newS]) {↵
if (e[id].f != e[id].c) {↵
printf("NO\n");↵
return;↵
}↵
}↵
↵
vvi ansv, ansc;↵
ansv = ansc = vvi(n, vi(m));↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
int dir = follow[i][j];↵
↵
if (dir != -1) {↵
int ni = i + dx[dir], nj = j + dy[dir];↵
ansv[i][j] = arr[i][j] - arr[ni][nj];↵
ansc[i][j] = dir;↵
}↵
}↵
}↵
↵
for (Edge it : e) {↵
int v = it.v, to = it.to;↵
↵
if (max(v, to) < n * m && it.f == it.c && it.c == 1) {↵
int ax = v / m, ay = v % m;↵
int bx = to / m, by = to % m;↵
ansv[ax][ay] = arr[ax][ay] - 1;↵
ansv[bx][by] = 1;↵
↵
for (int dir = 0; dir < 4; ++dir) {↵
if (mp(ax + dx[dir], ay + dy[dir]) == mp(bx, by)) {↵
ansc[ax][ay] = dir;↵
ansc[bx][by] = (dir + 2) % 4;↵
}↵
}↵
}↵
}↵
↵
printf("YES\n");↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
printf("%d%c", ansv[i][j], " \n"[j == m - 1]);↵
}↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
printf("%c%c", dc[ansc[i][j]], " \n"[j == m - 1]);↵
}↵
}↵
}↵
↵
int main() {↵
int tt;↵
scanf("%d", &tt);↵
↵
while (tt--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
