Codeforces Round #664 Editorial
Difference between en8 and en9, changed 11,216 character(s)
Thank you for participating, and I hope you enjoyed the problems!↵

Solutions will be updated after system testing...↵

## [problem:1395A]↵

Idea: [user:dqa2020,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1395A]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...↵
</spoiler>↵

## [problem:1395B]↵

Idea: [user:Xiejiadong,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1395B]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...↵
</spoiler>↵

## [problem:1395C]↵

Idea: [user:xryjr233,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1395C]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...↵
</spoiler>↵

## [problem:1394A]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394A]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...↵
</spoiler>↵

## [problem:1394B]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394B]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...↵
</spoiler>↵

## [problem:1394C]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394C]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...↵
</spoiler>↵

## [problem:1394D]↵

Idea: [user:ZZZZZZZZZZZZZZZZZZ,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394D]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...↵
</spoiler>↵

## [problem:1394E]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394E]↵
</spoiler>↵

<spoiler summary="Solution">↵
Pending...

~~~~~↵
def check(r,g,b,w):↵
    return False if r%2 + g%2 + b%2 + w%2 > 1 else True↵

if __name__ == '__main__':↵
    T = int(input())↵
    for ttt in range(T):↵
        r,g,b,w = map(int,input().split())↵
        if check(r,g,b,w):↵
            print("Yes")↵
        elif r>0 and g>0 and b>0 and check(r-1,g-1,b-1,w+1):↵
            print("Yes")↵
        else :↵
            print("No")↵
~~~~~↵


</spoiler>↵

## [problem:1395B]↵

Idea: [user:Xiejiadong,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1395B]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

const int maxn = 100;↵
int n, m, a, b;↵
bool row[maxn + 3], vis[maxn + 3][maxn + 3];↵

int main() {↵
scanf("%d %d %d %d", &n, &m, &a, &b);↵
for (int i = 1; i <= n; i++) {↵
if (i > 1) for (int j = 1; j <= n; j++) if (!row[j]) { a = j; break; }↵
row[a] = true;↵
printf("%d %d\n", a, b);↵
vis[a][b] = true;↵
for (int j = 1; j < m; j++) {↵
for (int k = 1; k <= m; k++) if (!vis[a][k]) { b = k; break; }↵
printf("%d %d\n", a, b);↵
vis[a][b] = true;↵
}↵
}↵
return 0;↵
} ↵
~~~~~↵


</spoiler>↵

## [problem:1395C]↵

Idea: [user:xryjr233,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1395C]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include<bits/stdc++.h>↵
#define ci const int&↵
using namespace std;↵
int n,m,p[210],d[210],ans;↵
bool Check(ci x){↵
for(int i=1;i<=n;++i){↵
for(int j=1;j<=m;++j)if(((p[i]&d[j])|x)==x)goto Next;↵
return 0;↵
Next:;↵
}↵
return 1;↵
}↵
int main(){↵
scanf("%d%d",&n,&m);↵
for(int i=1;i<=n;++i)scanf("%d",&p[i]);↵
for(int i=1;i<=m;++i)scanf("%d",&d[i]);↵
ans=(1<<9)-1;↵
for(int i=8;i>=0;--i)Check(ans^(1<<i))?ans^=(1<<i):0;↵
printf("%d",ans);↵
return 0;↵
}↵
~~~~~↵


</spoiler>↵

## [problem:1394A]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394A]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
#define rep(i, a, b) for (int i = (a); i <= int(b); i++)↵
using namespace std;↵

typedef long long ll;↵
const int maxn = 1e5;↵
int n, d, m, k, l;↵
ll a[maxn + 5], b[maxn + 5];↵

void solve(ll a[], int n) {↵
sort(a + 1, a + n + 1);↵
reverse(a + 1, a + n + 1);↵
rep(i, 1, n) a[i] += a[i - 1];↵
}↵

int main() {↵
scanf("%d %d %d", &n, &d, &m);↵
for (int i = 0, x; i < n; i++) {↵
scanf("%d", &x);↵
if (x > m) a[++k] = x;↵
else b[++l] = x;↵
}↵
if (k == 0) {↵
ll s = 0;↵
rep(i, 1, n) s += b[i];↵
printf("%lld\n", s);↵
exit(0);↵
}↵
solve(a, k);↵
solve(b, l);↵
fill(b + l + 1, b + n + 1, b[l]);↵
ll res = 0;↵
rep(i, (k + d) / (1 + d), k) if (1ll * (i - 1) * (d + 1) + 1 <= n) {↵
res = max(res, a[i] + b[n - 1ll * (i - 1) * (d + 1) - 1]);↵
}↵
printf("%lld\n", res);↵
return 0;↵
} ↵
~~~~~↵


</spoiler>↵

## [problem:1394B]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394B]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include<cstdio>↵
#include<algorithm>↵
#include<cctype>↵
#include<vector>↵
#define pb push_back↵
#define nd second↵
#define st first↵
using namespace std;↵
#define G getchar()↵
int read()↵
{↵
int x=0; bool flg=false; char ch=G;↵
for (;!isdigit(ch);ch=G) if (ch=='-') flg=true;↵
for (;isdigit(ch);ch=G) x=(x<<3)+(x<<1)+(ch^48);↵
return flg?-x:x;↵
}↵
#undef G↵
typedef long long ll;↵

int n,m,k;↵
struct Edge{↵
int to,nxt;↵
}edge[200010];↵
int cnt,last[200010],deg[200010];↵
inline void addedge(int x,int y){↵
edge[++cnt]=(Edge){y,last[x]},last[x]=cnt;↵
}↵
typedef pair<int,int> P;↵
vector<P> d[200010];↵
ll S[15][15];↵
int id[15][15],idtot;↵
int ans;↵
int c[15];↵
void dfs(int x){↵
if (x>k){↵
ll T=0;↵
for (int i=1;i<=k;i++) T|=1LL<<id[i][c[i]];↵
for (int i=1;i<=k;i++) if (T&S[i][c[i]]) return;↵
// puts("===========");↵
// for (int i=1;i<=k;i++) printf("%d ",c[i]); puts("");↵
// for (int i=1;i<=n;i++) printf("%d -> %d %d (%d)\n",i,deg[i],c[deg[i]],d[i][c[deg[i]]-1].nd);↵
ans++;↵
return;↵
}↵
for (int i=1;i<=x;i++) c[x]=i,dfs(x+1);↵
}↵
int main()↵
{↵
n=read(),m=read(),k=read();↵
for (int i=1;i<=k;i++)↵
for (int j=1;j<=i;j++)↵
id[i][j]=++idtot;↵
for (int i=1;i<=m;i++){↵
int x=read(),y=read(),v=read();↵
addedge(y,x); deg[x]++;↵
d[x].pb((P){v,y});↵
}↵
for (int i=1;i<=n;i++) sort(d[i].begin(),d[i].end());↵
for (int i=1;i<=n;i++){↵
static int bin[15][15];↵
for (int u=1;u<=k;u++)↵
for (int v=1;v<=u;v++)↵
bin[u][v]=0;↵
// printf("invalid set of %d\n",i);↵
ll T=0;↵
for (int j=last[i],v;j;j=edge[j].nxt){↵
v=edge[j].to;↵
int p=0; while (d[v][p].nd^i) p++; p++;↵
T|=1LL<<id[deg[v]][p];↵
bin[deg[v]][p]++;↵
// printf("ins %d %d\n",deg[v],p);↵
}↵
for (int j=last[i],v;j;j=edge[j].nxt){↵
v=edge[j].to;↵
int p=0; while (d[v][p].nd^i) p++; p++;↵
if (bin[deg[v]][p]==1) S[deg[v]][p]|=T^(1LL<<id[deg[v]][p]);↵
else S[deg[v]][p]|=T;↵
}↵
}↵
dfs(1);↵
printf("%d\n",ans);↵
return 0;↵
}↵
~~~~~↵


</spoiler>↵

## [problem:1394C]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394C]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
//by Sshwy↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)↵
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)↵
const int INF=1e9;↵

int n;↵

int main(){↵
    cin>>n;↵
    int lx=INF,rx=-INF,ly=INF,ry=-INF,lz=INF,rz=-INF;↵
    FOR(i,1,n){↵
        string s;↵
        cin>>s;↵
        int x=0,y=0;↵
        for(char c:s){↵
            if(c=='B')++x;↵
            else ++y;↵
        }↵
        //printf("%d %d\n",x,y);↵
        lx=min(lx,x), rx=max(rx,x);↵
        ly=min(ly,y), ry=max(ry,y);↵
        lz=min(lz,x-y), rz=max(rz,x-y);↵
    }↵

    int ans=INF,ax=0,ay=0,az=0;↵
    auto calc = [&](){↵
        int l=0,r=lz-(lx-ry),mid;↵
        auto check = [&](int a){↵
            return lx+a+a>=rx && lx-ry+a+a+a>=rz && ry-a-a<=ly;↵
        };↵
        if(check(r)==0)return INF;↵
        while(l<r)mid=(l+r)>>1, check(mid)?r=mid:l=mid+1;↵
        return l;↵
    };↵
    FOR(_,1,6){↵
        assert(lx<=rx && ly<=ry && lz<=rz);↵
        int v=calc();↵
        if(v<ans){↵
            ans=v;↵
            ax=lx+v, ay=ry-v, az=ax-ay;↵
        }↵
        int Lx=ly,Rx=ry,Ly=-rz,Ry=-lz,Lz=lx,Rz=rx;↵
        lx=Lx, rx=Rx, ly=Ly, ry=Ry, lz=Lz, rz=Rz;↵
        int Ax=ay,Ay=-az,Az=ax;↵
        ax=Ax,ay=Ay,az=Az;↵
    }↵
    cout<<ans<<endl;↵
    FOR(i,1,ax)cout<<'B';↵
    FOR(i,1,ay)cout<<'N';↵
    cout<<endl;↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

## [problem:1394D]↵

Idea: [user:ZZZZZZZZZZZZZZZZZZ,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394D]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include<bits/stdc++.h>↵
#define ci const int&↵
using namespace std;↵
const long long INF=1e18;↵
struct edge{↵
int t,nxt,dir;↵
}e[400010];↵
int n,h[200010],c[200010],u,v,be[200010],vis[200010],ar[200010],sz,cnt,t;↵
long long f[200010],g[200010];↵
priority_queue<long long>pq;↵
void add(ci x,ci y,ci d){↵
e[++cnt]=(edge){y,be[x],d},be[x]=cnt;↵
}↵
long long Calc(ci x,ci st){↵
//cout<<"CALC "<<x<<" "<<st<<"\n";↵
if(!sz)return (!!st)*c[x];↵
int tmp=st+sz;↵
long long a1,a2;↵
a1=1ll*((st>0)+sz)*c[x];↵
while(!pq.empty())pq.pop();↵
for(int i=1;i<=sz;++i)f[ar[i]]!=INF?pq.push(f[ar[i]]-g[ar[i]]+c[x]),a1+=f[ar[i]]:(a1+=g[ar[i]]-c[x],tmp-=2);↵
//cout<<"A1="<<a1<<",tmp="<<tmp<<"\n";↵
while(!pq.empty()&&tmp>1&&pq.top()>0)a1-=pq.top(),pq.pop(),tmp-=2;↵
if(tmp<0)a1=INF;↵
a2=1ll*((st<0)+sz)*c[x],tmp=st-sz;↵
while(!pq.empty())pq.pop();↵
for(int i=1;i<=sz;++i)g[ar[i]]!=INF?pq.push(g[ar[i]]-f[ar[i]]+c[x]),a2+=g[ar[i]]:(a2+=f[ar[i]]-c[x],tmp+=2);↵
//cout<<"A2="<<a2<<",tmp="<<tmp<<"\n";↵
while(!pq.empty()&&tmp<-1&&pq.top()>0)a2-=pq.top(),pq.pop(),tmp+=2;↵
if(tmp>0)a2=INF;↵
//cout<<"a1="<<a1<<",a2="<<a2<<"\n";↵
return min(a1,a2);↵
}↵
void TDP(ci x){↵
vis[x]=1;↵
int td=0;↵
for(int i=be[x];i;i=e[i].nxt)if(!vis[e[i].t])TDP(e[i].t);↵
else td=e[i].dir;↵
sz=0;↵
for(int i=be[x];i;i=e[i].nxt)if(!vis[e[i].t])ar[++sz]=e[i].t;↵
//cout<<"DP"<<x<<" sz="<<sz<<"\n";↵
if(x==1)f[x]=Calc(x,0);↵
else f[x]=(td!=1?Calc(x,-1):INF),g[x]=(td!=-1?Calc(x,1):INF);↵
//cout<<"F "<<x<<"="<<f[x]<<",g="<<g[x]<<"\n";↵
vis[x]=0;↵
}↵
int main(){↵
scanf("%d",&n);↵
for(int i=1;i<=n;++i)scanf("%d",&c[i]);↵
for(int i=1;i<=n;++i)scanf("%d",&h[i]);↵
for(int i=1;i<n;++i)scanf("%d%d",&u,&v),t=(h[u]>=h[v]?(h[u]>h[v]):-1),add(u,v,t),add(v,u,-t);↵
TDP(1),printf("%lld",f[1]);↵
return 0;↵
}↵
~~~~~↵


</spoiler>↵

## [problem:1394E]↵

Idea: [user:sshwyR,2020-08-12]↵

<spoiler summary="Tutorial">↵
[tutorial:1394E]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
//by Sshwy↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define pb push_back↵
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)↵
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)↵

const int N=1e5+5;↵
int n,a[N],xyx,q[N],c[N],p[N];↵
vector<int> v[N];↵

int pos;↵

void get_v(int pos){↵
    v[pos].clear();↵
    if(pos==1)return;↵
    if(a[pos]==a[pos-1])v[pos].pb(2);↵
    for(auto x:v[pos-1])if(a[pos]==a[pos-x-1])v[pos].pb(x+2);↵
}↵
bool check_even_pal(int L,int R){↵
    assert(R<=pos);↵
    for(auto x:v[R])if(x==R-L+1)return 1;↵
    return 0;↵
}↵

int qry(){↵
    int res=xyx+c[pos];↵
    int cur=pos;↵
    while(p[cur] && q[pos]<=cur-p[cur]/2){↵
        cur-=p[cur]/2;↵
        ++res;↵
    }↵
    return res;↵
}↵

int main(){↵
    scanf("%d",&n);↵
    q[0]=1;↵
    FOR(i,1,n){↵
        ++pos;↵
        scanf("%d",&a[pos]);↵
        get_v(pos);↵
        int x;↵
        if(v[pos].size() && (x=v[pos][0], check_even_pal(pos-x/2-x+1,pos-x/2))){↵
            pos-=x;↵
            xyx+=2;↵
        }else {↵
            p[pos]=v[pos].size()? v[pos][0]:0;↵
            q[pos]=q[pos-1],c[pos]=c[pos-1];↵
            if(check_even_pal(q[pos],pos)){↵
                q[pos]+=(pos-q[pos]+1)/2;↵
                c[pos]++;↵
            }↵
        }↵
        printf("%d%c",qry()," \n"[i==n]);↵
    }↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en14 English sshwyR 2020-08-12 23:55:45 8
en13 English sshwyR 2020-08-12 22:34:46 522
en12 English sshwyR 2020-08-12 22:03:54 1947
en11 English sshwyR 2020-08-12 21:07:49 2262
en10 English sshwyR 2020-08-12 21:03:07 311
en9 English sshwyR 2020-08-12 21:01:03 11216 Tiny change: 'lution">\nPending...\n</spoile' -> 'lution">\n[submission:89608526]\n</spoile'
en8 English sshwyR 2020-08-12 20:01:27 48 (published)
en7 English sshwyR 2020-08-12 20:00:14 53
en6 English sshwyR 2020-08-12 19:58:44 42
en5 English sshwyR 2020-08-12 19:58:12 222 Tiny change: 'torial">\nPending...\n</spoile' -> 'torial">\n\n</spoile'
en4 English sshwyR 2020-08-12 07:28:06 1
en3 English sshwyR 2020-08-12 07:27:07 497
en2 English sshwyR 2020-08-12 07:23:13 917 Tiny change: ' problems!' -> ' problems!\n\n## [problem:1391A]'
en1 English sshwyR 2020-08-12 07:15:39 96 Initial revision (saved to drafts)