AOJ 1008

問題自体は簡単。

だが、重要なのは1位の人のコードの速さ。
2位以降は0.4秒付近なのに、1位が0.06秒。ヤバい。

ちょっとこれに対抗するために頑張りました。

問題は

n個の数値の内、n/2個より多く同じ数値があったらその数値を出力しなさい

というもの。

とりあえず、mapでカウントで通る。
だがこれだと0.7sくらい。

次にhashを使うが、全然遅い。

ハッシュ値かぶらないだろーという仮定でやったら意外と通る。
最終的にハッシュ関数は a & 0x7f というので行けた。
そうすると、0.2秒くらい。

ここまで来ると入力が遅い気がする。
ということで入力のパースだけするプログラム送ると0.2秒。
つまりほぼ入力のパースの時間しかかかってない。

この時入力は

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

でintにパースしていました。
getcharが遅いと踏んで、自分でバッファリングしてみる。
これで0.05秒で単独一位!

ということで最終コードはこちら。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char buffer[4 * 1024 * 1024];
int pos = 0;
int end = 0;

int mygetchar(){
  if(pos == end){
    end = read(0, buffer, sizeof(buffer));
    pos = 0;
  }
  return buffer[pos++];
}

__attribute__((always_inline)) int getInt(){
  int ret = 0, c;
  c = mygetchar();
  while(!isdigit(c)) c = mygetchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = mygetchar();
  }
  return ret;
}

#define mask (0x7F)
int cnt[mask];

int main(){
  int n, i;
  while(n = getInt()){
    const int n2 = n / 2;
    memset(cnt, 0, sizeof(cnt));

    for(i = 0; i < n; i++){
      int a = getInt();

      if(++cnt[a & mask] > n2){
	printf("%d\n", a);
	for(++i; i < n; i++)
	  getInt();
	goto end;
      }
    }

    puts("NO COLOR");

  end:;
  }
  return 0;
}