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; }