JOI春合宿2012 Day2

昨日の問題が簡単に見えるレベル
問題の内容は省略します。

Broadcasting

適当にやったら案の定残念な点数(49点)だった。きゅうりぱないなのっ！

Constellation

凸包とって適当にほげほげしたら 100 点とれた。点数分布がきれいに0点と100点に分かれていてどんびき

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long i64;
const i64 MOD = 1000000007;

struct star
{
  i64 x, y, t;
  star(){ }
  star(int _x, int _y, int _t) {x = _x; y = _y; t = _t; }
};
inline bool operator<(const star& A, const star& B)
{
  return A.x < B.x || (A.x == B.x && A.y < B.y);
}

int N;
star st[100000];
vector<star> cv;

int ccw(star& A, star& B, star& C)
{
  i64 tmp = (B.y - A.y) * (C.x - A.x) - (B.x - A.x) * (C.y - A.y);
  return tmp>0 ? 1 : -1;
}

void make_convex()
{
  sort(st, st+N);
  cv.push_back(st[0]);
  cv.push_back(st[1]);
  for(int i=2;i<N;i++){
    while(cv.size() >= 2 && ccw(cv[cv.size()-2], cv[cv.size()-1], st[i])==-1)
      cv.pop_back();
    cv.push_back(st[i]);
  }
  cv.push_back(st[N-2]);
  for(int i=N-3;i>=0;i--){
    while(cv.size() >= 2 && ccw(cv[cv.size()-2], cv[cv.size()-1], st[i])==-1)
      cv.pop_back();
    cv.push_back(st[i]);
  }
  cv.pop_back();

  //for(int i=0;i<cv.size();i++) printf("%lld %lld\n", cv[i].x, cv[i].y);
}

int As[200010], Bs[200010];

int main()
{
  scanf("%d", &N);
  for(int i=0;i<N;i++)
    scanf("%lld%lld%lld", &(st[i].x), &(st[i].y), &(st[i].t));

  make_convex();

  i64 ret_a = 1;
  int arbitrary = 0;
  int cont1=0, cont2=0;
  for(int i=0;i<N;i++){
    if(st[i].t==0) ++arbitrary;
    if(st[i].t==1) ++cont1;
    if(st[i].t==2) ++cont2;
  }
  for(int i=0;i<cv.size();i++){
    if(cv[i].t==0) --arbitrary;
    if(cv[i].t==1) --cont1;
    if(cv[i].t==2) --cont2;
  }
  while(arbitrary){ ret_a = (ret_a*2)%MOD; --arbitrary; }
  cont1 = !!cont1;
  cont2 = !!cont2;

  i64 ret = 0;
  int M = cv.size();

  As[0] = 0;
  for(int i=1;i<=2*M;i++) As[i] = As[i-1] + ((cv[i%M].t==1) ? 1 : 0);
  Bs[0] = 0;
  for(int i=1;i<=2*M;i++) Bs[i] = Bs[i-1] + ((cv[i%M].t==2) ? 1 : 0);
  for(int i=0;i<M;i++){
    int jMin, jMax;
    jMin = (lower_bound(As, As+(2*M+1), As[i+M]) - As) - i;
    jMax = (upper_bound(Bs, Bs+(2*M+1), Bs[i]) - Bs) - i - 1;
    jMin = max(jMin, 1);
    jMax = min(jMax, M-1);
    ret += (ret_a * (i64)max(0, jMax - jMin + 1)) % MOD;
    ret %= MOD;
  }

  ret += 2 * (ret_a - 1) + cont1 + cont2;
  for(int i=0;i<M;i++){
    if(cv[i].t==1){
      ret -= ret_a - 1 + cont1;
      break;
    }
  }
  for(int i=0;i<M;i++){
    if(cv[i].t==2){
      ret -= ret_a - 1 + cont2;
      break;
    }
  }
  printf("%lld\n", ret % MOD);

  return 0;
}

Rotate

思いつかなくて「やるだけ」やったら 10 点で絶望。
コードは載せるまでもない
リストの張替え O(QN) で満点が取れるらしい。定数倍最適化で 80 点が取れるらしくてどんびき