Tamflexの貯蔵庫

やる気のない備忘録

arc 051

arc051.contest.atcoder.jp

A問題

円の中心が長方形の内側か外側にあるかで場合分けすれば解けます.

int main()
{
  P p; double r; cin>>p.x>>p.y>>r;
  P q1,q2; cin>>q1.x>>q1.y>>q2.x>>q2.y;
  P q = (q1+q2)/2;
  P q3(q1.x,q2.y);
  P q4(q2.x,q1.y);
  bool red, blue;
  if(p.x>q1.x&&p.x<q2.x&&p.y>q1.y&&p.y<q2.y)
  {
    bool f=p.x-q1.x>=r&&q2.x-p.x>=r&&p.y-q1.y>=r&&q2.y-p.y>=r;
    if(f){red = false; blue=true;}
    else
    {
      bool g=((q1-p).norm()<=r)&&((q2-p).norm()<=r)&&((q3-p).norm()<=r)&&((q4-p).norm()<=r);
      if(g){red = true; blue=false;}
      else {red = true; blue=true;}
    }
  }
  else
  {
    bool f=((q1-p).norm()<=r)&&((q2-p).norm()<=r)&&((q3-p).norm()<=r)&&((q4-p).norm()<=r);
    if(f){red = true; blue = false;}
    else{red = true; blue = true;}
  }
  cout << (red?"YES":"NO") << endl;
  cout << (blue?"YES":"NO") << endl;
  return 0;
}

B問題

逆算しましょう

int main()
{
  ll k; cin >> k;
  ll a, b, ta, tb;
  a = 2; b = 0;
  REP(i,k+1)
  {
    ta = a + b;
    tb = a;
    a = ta;
    b = tb;
  }
  cout << a << " " << b << endl;
}

C問題

数列のすべての数が少なくとも一回掛け算されればあとは数の順序が環状になることを利用しましょう.
注意すべきはA=1の時でこの時は特殊なので場合分けしましょう.
あとはべき乗の評価は例のアルゴリズムを使えばO(log(B))で行けそうです.

int main()
{
  ll n, a, b; cin >> n >> a >> b;
  vector<bool> T(n,false);
  vector<Modulo<MOD>> U(n);
  priority_queue<pair<ll,int>> pq;
  REP(i,n)
  {
    int t; cin >> t;
    pq.push(make_pair(-t,i));
  }
  ll cnt = 0;
  while(cnt < b)
  {
    if(a==1) break;
    bool f = true;
    REP(i,n) if(!T[i]) {f = false; break;}
    if(f) break;
    cnt++;
    auto t = pq.top(); pq.pop();
    t.first *= a; T[t.second] = true;
    pq.push(t);
  }
  REP(i,n)
  {
    auto t = pq.top(); pq.pop();
    U[i] = Modulo<MOD>(-t.first);
  }
  if(cnt==0) REP(i,n) cout << (ll) U[i] << endl;
  else
  {
    Modulo<MOD> c = Modulo<MOD>(a).power((b-cnt)/n);
    REP(i,n) U[i]*=c;
    REP(i,((b-cnt)%n)) U[i] *= a;
    REP(i,n) cout << (ll) U[(i+(b-cnt)%n)%n] << endl;
  }
  return 0;
}