Codeforces Round #684[Div1 and Div2] Editorial
Разница между en16 и en17, 3 символ(ов) изменены
We want to mention [user:BamiTorabi,2020-11-18] and [user:amoo_safar,2020-11-18] who we thank for helping us with translating the problems and writing the tutorials.and we want to apologize for div1 A2 and B hopefully you will forgive us :( .↵

[tutorial:1440A]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵

<spoiler summary="official solution">↵

~~~~~↵
//                                In The Name Of Allah↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define ret(n) return cout << n, 0↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
#define ll long long↵
#define ld long double↵
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵

const int N = 3e5 + 100, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;↵
typedef pair <int, int> pii;↵

void solve() {↵
int n, c0, c1, t;↵
string s;↵
cin >> n >> c0 >> c1 >> t >> s;↵
int ans = 0;↵
for(auto u : s) {↵
if(u == '0') ↵
ans += min(c0, c1 + t);↵
else ↵
ans += min(c1, c0 + t);↵
}↵
cout << ans << endl;↵
}↵

int32_t main() {↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵

</spoiler>↵


[tutorial:1440B]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵

<spoiler summary="official solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
typedef long long int ll;↵
typedef long double ld;↵
#define pb push_back↵
#define pii pair < int , int >↵
#define F first↵
#define S second↵
#define endl '\n'↵
#define int long long↵
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")↵
#define kill(x) return cout<<x<<'\n', 0;↵
using namespace std;↵
const int N=2e5+100;↵
ll a[N];↵
int Main(){↵
    ll n, k;↵
    cin >> k >> n;↵
    for (int i=1;i<=n*k;i++){↵
        cin >> a[i];↵
    }↵
    ll x=(k+1)/2 - 1;↵
    x = k - x;↵
    ll z=n*k+1;↵
    ll ans=0;↵
    while(n--){↵
        z-=x;↵
        if (z<=0) break;↵
        ans+=a[z];↵
    }↵
    cout << ans << endl;↵
}↵
int32_t main(){↵
    ll t;↵
    cin >> t;↵
    while(t--){↵
        Main();↵
    }↵
}↵
~~~~~↵

</spoiler>↵


[tutorial:1439A2]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵

<spoiler summary="official solution">↵

~~~~~↵
//                             In The Name Of Allah↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define ret(n) return cout << n, 0↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
#define ll long long↵
#define ld long double↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵

const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;↵
typedef pair <int, int> pii;↵
char c[N][N];↵
bool cnt[N][N];↵

struct node {int x1, y1, x2, y2, x3, y3;} p[5];↵
vector <node> v;↵

void upd(int x, int y, int tp, bool is) {↵
    if(is)↵
        v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3});↵
    else ↵
        cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1;↵
}↵

void solve() {↵
int n, m, od = 0;↵
v.clear();↵
cin >> n >> m;↵
for(int i = 1; i <= n; i++) {↵
for(int j = 1; j <= m; j++) {↵
cin >> c[i][j];↵
if(c[i][j] == '1')↵
od++, cnt[i][j] = true;↵
else↵
    cnt[i][j] = false;↵
}↵
}↵
if(od == 0) {↵
cout << 0 << endl;↵
return;↵
}↵
if(n == 1 || m == 1) {↵
cout << -1 << endl;↵
return;↵
}↵
    for(int i = 1; i <= n - 2; i++) {↵
for(int j = 1; j <= m; j++) {↵
if(cnt[i][j]) {↵
    if(j != m) {↵
        v.pb({i, j, i + 1, j, i + 1, j + 1});↵
        cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1;↵
    } ↵
    else {↵
        v.pb({i, j, i + 1, j, i + 1, j - 1});↵
        cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1;↵
    }↵
}↵
}↵
}↵
for(int i = 1; i <= m - 2; i++) {↵
    if(cnt[n - 1][i]) {↵
        v.pb({n - 1, i, n - 1, i + 1, n, i + 1});↵
        cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; ↵
    }↵
    if(cnt[n][i]) {↵
        v.pb({n, i, n - 1, i + 1, n, i + 1});↵
        cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; ↵
    }↵
}↵
for(int msk = 0; msk < (1 << 4); msk++) {↵
    for(int j = 0; j < 4; j++) ↵
       if(msk & (1 << j))↵
           upd(n - 1, m - 1, j, 0);↵
    if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) {↵
        for(int j = 0; j < 4; j++) ↵
            if(msk & (1 << j))↵
                upd(n - 1, m - 1, j, 1);↵
        break;↵
    }↵
    for(int j = 0; j < 4; j++)↵
        if(msk & (1 << j))↵
            upd(n - 1, m - 1, j, 0);↵
}↵
cout << (int)v.size() << endl;↵
for(auto u : v)↵
        cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl;↵
}↵

int32_t main(){↵
use_fast;↵
    p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0};↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵

</spoiler>↵


[tutorial:1439B]↵
Prepared by [user:Alishahali1382,2020-11-18]↵

<spoiler summary="official solution">↵

~~~~~↵
//                             In The Name Of Allah                                           ↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
//#define int long long↵
#define ld long double↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵
const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22;↵
typedef pair <int, int> pii;↵
int mark[N], deg[N], ct[N];↵
bool ans[N], can[N];↵
vector <int> v[N], A;↵
vector <pii> ch[N];↵
bool cmp(int x, int y) {↵
return mark[x] < mark[y];↵
}↵

void solve() {↵
int n, m, k;↵
cin >> n >> m >> k;↵
A.clear();↵
for(int i = 0; i <= n; i++)↵
    v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false;↵
for(int i = 0; i < m; i++) {↵
int x, y;↵
cin >> x >> y;↵
v[x].pb(y);↵
v[y].pb(x);↵
}↵
if(k > 500) {↵
   cout << -1 << endl;↵
   return;↵
}↵
set <pii> st;↵
for(int i = 1; i <= n; i++)↵
st.insert({deg[i] = (int)v[i].size(), i});↵
int cnt = 1;↵
while((int)st.size()) {↵
pii p = *st.begin();↵
if(p.ff >= k) {↵
cout << 1 << " " << (int)st.size() << endl;↵
for(auto u : st)↵
cout << u.ss << " ";↵
cout << endl;↵
return;↵
}↵
else {↵
st.erase(p);↵
mark[p.ss] = cnt;↵
for(auto u : v[p.ss])↵
if(!mark[u])↵
st.erase({deg[u], u}), st.insert({--deg[u], u});↵
A.pb(p.ss);↵
}↵
cnt++;↵
}↵
for(auto i : A) {↵
int nxt = 0;↵
for(auto u : v[i]) ↵
if(mark[u] > mark[i])↵
ct[nxt++] = u, can[u] = true;↵
for(auto u : ch[i]) ↵
if(!can[u.ff])↵
ans[u.ss] = false;↵
for(int j = 0; j < nxt; j++)↵
can[ct[j]] = false;↵
if(nxt != k - 1)↵
continue;↵
ans[i] = true;↵
sort(ct, ct + nxt, cmp);↵
for(int j = 0; j < nxt; j++)↵
for(int k = j + 1; k < nxt; k++)↵
ch[ct[j]].pb({ct[k], i});↵
}↵
for(auto i : A) {↵
if(!ans[i])↵
continue;↵
cout << 2 << endl;↵
cout << i << " ";↵
for(auto u : v[i])↵
if(mark[u] > mark[i])↵
cout << u << " ";↵
cout << endl;↵
return;↵
}↵
cout << -1 << endl;↵
return;↵
}↵

int32_t main() {↵
use_fast;↵
int t;↵
    cin >> t;↵
    while(t--)↵
        solve();↵
return 0;↵
}↵
~~~~~↵


</spoiler>↵



[tutorial:1439C]↵
prepared by [user:Mehrdad_sohrabi,2020-11-18]↵

<spoiler summary="official solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵

using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵

const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int mod=1000000007;↵
const int MAXN=200010, LOG=20;↵

ll n, m, k, u, v, x, y, t, a, b, ans;↵
ll A[MAXN];↵
ll seg[MAXN<<2], lazy[MAXN<<2];↵
int Mn[MAXN<<2], Mx[MAXN<<2];↵

void Build(int id, int tl, int tr){↵
if (tr-tl==1){↵
Mn[id]=Mx[id]=seg[id]=A[tl];↵
return ;↵
}↵
int mid=(tl+tr)>>1;↵
Build(id<<1, tl, mid);↵
Build(id<<1 | 1, mid, tr);↵
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);↵
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);↵
seg[id]=seg[id<<1] + seg[id<<1 | 1]; ↵
}↵
inline void add_lazy(int id, int len, ll val){↵
Mn[id]=val;↵
Mx[id]=val;↵
lazy[id]=val;↵
seg[id]=len*val;↵
}↵
inline void shift(int id, int tl, int tr){↵
if (!lazy[id]) return ;↵
int mid=(tl+tr)>>1;↵
add_lazy(id<<1, mid-tl, lazy[id]);↵
add_lazy(id<<1 | 1, tr-mid, lazy[id]);↵
lazy[id]=0;↵
}↵
void Maximize(int id, int tl, int tr, int pos, ll val){↵
if (pos<=tl || val<=Mn[id]) return ;↵
if (tr<=pos && Mx[id]<=val){↵
add_lazy(id, tr-tl, val);↵
return ;↵
}↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1;↵
Maximize(id<<1, tl, mid, pos, val);↵
Maximize(id<<1 | 1, mid, tr, pos, val);↵
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);↵
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);↵
seg[id]=seg[id<<1] + seg[id<<1 | 1];↵
}↵
int BS1(int id, int tl, int tr, int pos, ll val){↵
if (tr<=pos || val<Mn[id]) return tr;↵
if (tr-tl==1) return tl;↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val);↵
if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val);↵
return tmp;↵
}↵
int BS2(int id, int tl, int tr, ll val){↵
if (seg[id]<=val) return tr;↵
if (tr-tl==1) return tl;↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val);↵
if (tmp<mid) return tmp;↵
return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]);↵
}↵
ll Get(int id, int tl, int tr, int l, int r){↵
if (r<=tl || tr<=l) return 0;↵
if (l<=tl && tr<=r) return seg[id];↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1;↵
return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r);↵
}↵

int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
cin>>n>>m;↵
for (int i=1; i<=n; i++) cin>>A[i];↵
Build(1, 1, n+1);↵
while (m--){↵
cin>>t>>x>>y;↵
if (t==1) Maximize(1, 1, n+1, x+1, y);↵
else{↵
ans=0;↵
while (1){↵
x=BS1(1, 1, n+1, x, y);↵
if (x==n+1) break ;↵
ll val=y+Get(1, 1, n+1, 1, x);↵
int xx=BS2(1, 1, n+1, val);↵
// buy [x, xx)↵
ans+=xx-x;↵
y-=Get(1, 1, n+1, x, xx);↵
x=xx;↵
}↵
cout<<ans<<"\n";↵
}↵
}↵

return 0;↵
}↵
~~~~~↵


</spoiler>↵

[tutorial:1439D]↵
prepared by [user:Mehrdad_sohrabi,2020-11-18]↵

<spoiler summary="official solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵

using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵

const ld eps=1e-7;↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int MAXN=505, LOG=20;↵

ll n, m, k, u, v, x, y, t, a, b, ans, mod;↵
ll dp1[MAXN], dp2[MAXN];↵
ll dp3[MAXN][MAXN], dp4[MAXN][MAXN];↵
ll C[MAXN][MAXN];↵

int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
cin>>n>>m>>mod;↵

for (int i=0; i<MAXN; i++){↵
C[i][0]=C[i][i]=1;↵
for (int j=1; j<i; j++) C[i][j]=(C[i-1][j] + C[i-1][j-1])%mod;↵
}↵
dp1[0]=1;↵
for (int n=1; n<MAXN; n++){↵
for (int i=1; i<=n; i++) dp1[n]=(dp1[n] + dp1[i-1]*dp1[n-i]%mod*C[n-1][i-1])%mod;↵
dp1[n]=(n+1)*dp1[n]%mod;↵
for (int i=1; i<=n; i++){↵
dp2[n]=(dp2[n] + (n+1)*C[n-1][i-1]%mod*((dp1[i-1]*dp2[n-i] + dp2[i-1]*dp1[n-i])%mod))%mod;↵
dp2[n]=(dp2[n] + C[n-1][i-1]*dp1[i-1]%mod*dp1[n-i]%mod*((i*(i-1)/2+(n-i)*(n-i+1)/2)%mod))%mod;↵
}↵
}↵

dp3[0][0]=1;↵
for (int n=1; n<MAXN; n++){↵
for (int m=0; m<n; m++){↵
dp3[n][m]=dp3[n-1][m];↵
dp4[n][m]=dp4[n-1][m];↵
for (int i=1; i<=m; i++){↵
dp3[n][m]=(dp3[n][m] + dp3[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;↵
dp4[n][m]=(dp4[n][m] + dp3[n-i-1][m-i]*dp2[i]%mod*C[m][i])%mod;↵
dp4[n][m]=(dp4[n][m] + dp4[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;↵
}↵
}↵
dp3[n][n]=dp1[n];↵
dp4[n][n]=dp2[n];↵
}↵

cout<<dp4[n][m]<<"\n"; ↵

return 0;↵
}↵
~~~~~↵

</spoiler>↵


<spoiler summary="O(n2) solution">↵

~~~~~↵
// And you curse yourself for things you never done↵
// Shayan.P  2020-08-29↵

#include<bits/stdc++.h>↵

#define F first↵
#define S second↵
#define PB push_back↵
#define sz(s) int((s).size())↵
#define bit(n,k) (((n)>>(k))&1)↵

using namespace std;↵

typedef long long ll;↵
typedef pair<int,int> pii;↵

const int maxn = 510, inf = 1e9 + 10, mod=1e9+7;↵

ll n, m;↵

ll Pow(ll a, ll b){↵
    b = (b + (mod-1)) % (mod-1); // to handle b == -1↵
    int ans=1;↵
    for(; b; b>>=1, a=a*a%mod) if (b&1) ans=ans*a%mod;↵
    return ans;↵
}↵
inline void add(ll &a, ll b){↵
    a = (a + b) % mod;↵
}↵
    ↵
ll fac[maxn], ifac[maxn];↵

ll C(ll n, ll k){↵
if (n<k || k<0) return 0;↵
return fac[n]*ifac[k]%mod*ifac[n-k]%mod;↵
}↵

int main(){↵
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();↵
    ↵
    fac[0] = 1;↵
    for(int i = 1; i < maxn; i++) fac[i]=fac[i-1]*i%mod;↵
    ifac[maxn-1] = Pow(fac[maxn-1], mod-2);↵
    for(int i = maxn-2; i >= 0; i--) ifac[i]=ifac[i+1]*(i+1)%mod;↵
    ↵
    cin >> n >> m;↵
    ++n; //!↵
    ↵
int ans = 0;↵
    for(ll bef = 0; bef < m; bef++){↵
for(ll w = 1; w + bef < m; w++){ // corner case : bef == 0↵
ll cnt1=Pow(w+1, w-1)*Pow(2, w)%mod;↵
ll cnt2=Pow(n-w-1, bef-1)*Pow(2, bef)%mod*(n-w-1-bef)%mod;↵
ll cnt=cnt1*cnt2%mod*C(w+bef, bef)%mod;↵
ll score=w*(w+1)%mod*n%mod;↵
ll after=Pow(n, m-bef-w-1)*Pow(2, m-bef-w-1) % mod;↵
ans=(ans + cnt*score%mod*after) % mod;↵
}↵
    }    ↵
    cout << 1ll * (n-m) * ans % mod * Pow(n, -1) % mod << "\n";↵
    return 0;↵
}↵

~~~~~↵


</spoiler>↵

[tutorial:1439E]↵
will be ready soon.↵

Prepared by [user:Alishahali1382,2020-11-18]↵

<spoiler summary="official solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵

using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵

const ld eps=1e-7;↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int mod=1000000007;↵
const int MAXN=400010, LOG=30;↵

int n, m, k, u, v, x, y, t, a, b, root, ans;↵
pii A[MAXN], V[MAXN];↵
int par[MAXN], sum[MAXN];↵
bool is[MAXN];↵
vector<int> G[MAXN], grundy;↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵

inline int GetH(pii p){ return p.first+p.second;}↵
inline pii GetPar(pii p, int k){↵
int x=p.first, y=p.second;↵
while (k){↵
int xx=(x&-x), yy=(y&-y);↵
if (!xx) xx=2*inf;↵
if (!yy) yy=2*inf;↵
int tmp=min(k, min(xx, yy));↵
k-=tmp;↵
if (xx<yy) x-=tmp;↵
else y-=tmp;↵
}↵
return {x, y};↵
}↵
inline int Zone(pii p, int n){↵
    if (p.first&(1<<(n-1))) return 2;↵
    if (p.second&(1<<(n-1))) return 1;↵
    return 0;↵
}↵
void dfs_order(vector<pii> &vec, int n=LOG) {↵
if (n==0 || vec.size()==0) return ;↵
vector<pii> v[3];↵
for (pii p:vec) {↵
int z=Zone(p, n);↵
p.first&=(1<<(n-1))-1;↵
p.second&=(1<<(n-1))-1;↵
v[z].pb(p);↵
    }↵
vec.clear();↵
for (int i:{0, 1, 2}) dfs_order(v[i], n-1);↵
for (pii p:v[0]) if (!p.first) vec.pb(p);↵
    for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))});↵
    for (pii p:v[0]) if (p.first) vec.pb(p);↵
    for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second});↵
}↵
pii Lca(pii u, pii v, int n=LOG) {↵
if (n==0) return {0, 0};↵
int zu = Zone(u, n), zv = Zone(v, n);↵
if (zu > zv) swap(u, v), swap(zu, zv);↵
u.first&=(1<<(n-1))-1;↵
u.second&=(1<<(n-1))-1;↵
v.first&=(1<<(n-1))-1;↵
v.second&=(1<<(n-1))-1;↵
if (zu == 1 && zv == 2) return {0, 0};↵
if (zu == 2 && zv == 2){↵
pii A = Lca(u, v, n-1);↵
return {A.first+(1<<(n-1)), A.second};↵
}↵
if (zu == 1 && zv == 1) {↵
pii A = Lca(u, v, n-1);↵
return {A.first, A.second+(1<<(n-1))};↵
}↵
if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1);↵
if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1);↵
return Lca(u, v, n-1);↵
}↵
inline int GetId(pii p){↵
return lower_bound(V, V+n, p)-V;↵
}↵
inline bool IsPar(pii u, pii v){↵
if (GetH(u)>GetH(v)) return 0;↵
return GetPar(v, GetH(v)-GetH(u))==u;↵
}↵
int dfs(int node){↵
for (int v:G[node]) sum[node]+=dfs(v);↵
return sum[node];↵
}↵

int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
vector<pii> vec;↵
cin>>m;↵
for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]);↵
sort(all(vec));↵
vec.resize(unique(all(vec))-vec.begin());↵
dfs_order(vec);↵
for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1]));↵
sort(all(vec));↵
vec.resize(unique(all(vec))-vec.begin());↵
dfs_order(vec);↵
n=vec.size();↵

debug("sorted")↵

for (int i=0; i<n; i++) V[i]=vec[i];↵
sort(V, V+n);↵
vector<int> stk={root=GetId(vec[0])};↵
for (int i=1; i<n; i++){↵
int v=GetId(vec[i]);↵
while (!IsPar(V[stk.back()], V[v])) stk.pop_back();↵
par[v]=stk.back();↵
G[stk.back()].pb(v);↵
stk.pb(v); ↵
}↵

for (int i=0; i<2*m; i+=2){↵
int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1]));↵
sum[u]++;↵
sum[v]++;↵
sum[lca]-=2;↵
is[lca]=1;↵
}↵
dfs(root);↵
for (int v=0; v<n; v++){↵
if (sum[v]){↵
grundy.pb(GetH(V[par[v]])+1);↵
grundy.pb(GetH(V[v])+1);↵
}↵
else if (is[v]){↵
grundy.pb(GetH(V[v]));↵
grundy.pb(GetH(V[v])+1);↵
}↵
}↵
sort(all(grundy));↵
vec.clear();↵
int last=-1;↵
for (int x:grundy){↵
if (last==-1){↵
if (vec.empty() || vec.back().second<x) last=x;↵
else{↵
last=vec.back().first;↵
vec.pop_back();↵
}↵
}↵
else{↵
if (last<x) vec.pb({last, x});↵
last=-1;↵
}↵
}↵
ans=2*vec.size();↵
if (ans && vec[0].first==0) ans--;↵
cout<<ans<<"\n";↵

return 0;↵
}↵
~~~~~↵


</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en23 Английский AliShahali1382 2020-12-11 07:48:40 0 (published)
en22 Английский AliShahali1382 2020-12-11 07:47:38 2 Tiny change: '0-11-18]\n\nEditoria' -> '0-11-18]\nEditoria'
en21 Английский AliShahali1382 2020-12-11 07:46:52 2 Tiny change: '0-11-18]\nEditoria' -> '0-11-18]\n\nEditoria'
en20 Английский AliShahali1382 2020-12-11 07:46:26 404 (saved to drafts)
en19 Английский AliShahali1382 2020-11-19 19:26:26 0 (published)
en18 Английский Mehrdad_Sohrabi 2020-11-19 02:05:41 0 (saved to drafts)
en17 Английский AliShahali1382 2020-11-19 00:03:36 3 (published)
en16 Английский AliShahali1382 2020-11-18 23:55:37 1607
en15 Английский AliShahali1382 2020-11-18 23:52:02 10653
en14 Английский AliShahali1382 2020-11-18 23:44:48 7601 (saved to drafts)
en13 Английский AliShahali1382 2020-11-18 17:39:04 2 Tiny change: 'dy soon.\nPrepared' -> 'dy soon.\n\nPrepared'
en12 Английский AliShahali1382 2020-11-18 02:20:11 69
en11 Английский Mehrdad_Sohrabi 2020-11-18 01:08:56 0 (published)
en10 Английский Mehrdad_Sohrabi 2020-11-18 01:08:28 246 Tiny change: ' A2 and B .\n[tutor' -> ' A2 and B hopefully you will forgive us :( .\n[tutor'
en9 Английский Mehrdad_Sohrabi 2020-11-18 00:57:44 120
en8 Английский Mehrdad_Sohrabi 2020-11-18 00:55:41 120 Tiny change: '0-11-18]\n[tutori' -> '0-11-18]\nJury solution: [subission:54047380]\n[tutori'
en7 Английский Mehrdad_Sohrabi 2020-11-18 00:49:26 264 Tiny change: 'rial:1439A]\nPrepare' -> 'rial:1439A2]\nPrepare'
en6 Английский AliShahali1382 2020-11-17 23:17:46 124
en5 Английский AliShahali1382 2020-11-17 23:17:01 6 Tiny change: 'tutorial:1159A]' -> 'tutorial:1440A]'
en4 Английский AliShahali1382 2020-11-17 23:16:43 4 Tiny change: 'tutorial:1439A]' -> 'tutorial:1159A]'
en3 Английский AliShahali1382 2020-11-17 23:11:37 23 Tiny change: 'heeyyyy' -> '[tutorial:1439A]'
en2 Английский AliShahali1382 2020-11-17 23:09:37 37
en1 Английский Mehrdad_Sohrabi 2020-11-17 23:07:47 16 Initial revision (saved to drafts)