Codeforces Round #400 (Div. 1 + Div. 2, combined)

遅延+鯖落ち+延長　これぞCodeforces（いいえ

【A. A Serial Killer】

がんばりましょう。
*(set.begin()+1)でバグって？？ってなった。
前はできた気がするんだけど…

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  set<string> ss;
  string a,b;
  cin>>a>>b;
  ss.insert(a);ss.insert(b);
  cout<<a<<" "<<b<<endl;
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a>>b;
    ss.erase(a);
    cout<<*ss.begin()<<" "<<b<<endl;
    ss.insert(b);
  }
  return 0;
}

【B. Sherlock and his girlfriend】

誤読して1WA。
素数判定やるだけなわけないでしょwと思ったらやるだけだった。
篩したけどO(NsqrtN)の愚直でも通りそう。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin>>n;
  int c[n],ans=0;
  memset(c,0,sizeof(c));
  for(int i=0;i<n;i++){
    c[i]++;
    ans=max(ans,c[i]);
    if(c[i]==1) for(int j=i;j<n;j+=i+2) c[j]=max(c[j],c[i]);
  }
  cout<<ans<<endl;
  for(int i=0;i<n;i++) cout<<c[i]<<" \n"[i==n-1];
  return 0;
}

【C. Molly's Chemicals】

k^m<=10^14になるmはO(log(NA))個しかないので、
mapに累積和をぶち込んでおいて全部決めうちするとO(Nlog(NA))になるよみたいな感じ。
k=1,-1がコーナー。2hackされた。
システムテストに通ったので圧倒的感謝。

うしさんと同じ部屋で笑ってたらhackされた。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int INF=1LL<<55LL;
  int n,k;
  cin>>n>>k;
  int m=0;
  int p[60];
  p[0]=1;
  if(k==1){
    m=1;
  }else if(k==-1){
    p[1]=-1;
    m=2;
  }else{
    for(int i=0;abs(p[i])<INF;i++){
      p[i+1]=p[i]*k;
      m=i+1;
    }
  }
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int ans=0,tmp=0;
  map<int,int> ma;
  for(int i=0;i<n;i++){
    ma[tmp]++;
    tmp+=a[i];
    for(int j=0;j<m;j++)
      if(ma.count(tmp-p[j]))
	ans+=ma[tmp-p[j]];
  }
  cout<<ans<<endl;
  return 0;
}

【D. The Door Problem】

「each door is controlled by exactly two switches.」なので
明らかに2SATやるだけ。蟻本見ながら書いた。
SCCはライブラリのやつ。UF解かしこいなあ。

int main(){
  int n,m;
  cin>>n>>m;
  int o[n];
  for(int i=0;i<n;i++) cin>>o[i];
  vector<int> s[n];
  for(int i=0;i<m;i++){
    int r;
    cin>>r;
    for(int j=0;j<r;j++){
      int k;
      cin>>k;
      k--;
      s[k].push_back(i);
    }
  }
  for(int i=0;i<n;i++){
    assert((int)s[i].size()==2);
    //cout<<o[i]<<" "<<s[i][0]<<" "<<s[i][1]<<endl;
    if(o[i]){
      add_edge(s[i][0],s[i][1]);
      add_edge(s[i][1],s[i][0]);
      add_edge(s[i][0]+m,s[i][1]+m);
      add_edge(s[i][1]+m,s[i][0]+m);
    }else{
      add_edge(s[i][0],s[i][1]+m);
      add_edge(s[i][1],s[i][0]+m);
      add_edge(s[i][0]+m,s[i][1]);
      add_edge(s[i][1]+m,s[i][0]);
    }
  }
  V=m*2;
  scc();
  for(int i=0;i<m;i++){
    //cout<<cmp[i]<<" "<<cmp[i+m]<<endl;
    if(cmp[i]==cmp[i+m]){
      cout<<"NO"<<endl;
      return 0;
    }
  }
  cout<<"YES"<<endl;
  return 0;
}

【全体】

oooo-- +1 3916points 440th
1574 -> 1712 (+138)
前回の太陽分回復した。
いつもこんぐらいできてればなあ。