#include #include #include #include #include #include #include #include #include using namespace std; using vi = vector; using vvi = vector>; int N = 1000; vvi freq(N, vi(N, 0)); std::mt19937 rand_src; int monte_carlo_rounds = 1000000; const int sample_size = 10000; int getInt() { int x; scanf("%d", &x); return x; } void random_initialize() { // Seed with a real random value, if available std::random_device r; std::seed_seq seed2{static_cast(time(0)), r(), r(), r(), r(), r(), r(), r(), r()}; rand_src = std::mt19937(seed2); } void good_shuffle(vi& data) { int c = (int) data.size(); for (int i = 0; i < c-1; ++i) { uniform_int_distribution dist(i, c-1); int j = dist(rand_src); swap(data[i], data[j]); } } void bad_shuffle(vi& data) { int c = (int) data.size(); uniform_int_distribution dist(0, c-1); for (int i = 0; i < c-1; ++i) { int j = dist(rand_src); swap(data[i], data[j]); } } vi get_rangearray(int n) { vi data; data.reserve(n); for (int i = 0; i < n; ++i) data.push_back(i); return data; } int getscore(const vi& data) { int score = 0; for (int i = 0; i < N; ++i) { if (data[i] < 0 || data[i] >= N) { fprintf(stderr, "out of range at %d\n", data[i]); } score += freq[i][data[i]]; } return score; } int transform(int x) { // return x <= 1 ? 0 : lround(log(x) * 100); return x; } void prepare_freq_array(int rounds) { fprintf(stderr, "Preparing frequency array: %d Monte-Carlo simulations...\n", rounds); for (int k = 0; k < rounds; ++k) { vi data = get_rangearray(N); bad_shuffle(data); for (int i = 0; i < N; ++i) freq[i][data[i]]++; } // transform data to improve accuracy for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) freq[i][j] = transform(freq[i][j]); fprintf(stderr, "Frequency array finished.\n"); } int get_cutoff_score() { fprintf(stderr, "Calculating cutoff scores...\n"); vi good_samples; good_samples.reserve(sample_size); for (int k = 0; k < sample_size; ++k) { vi data = get_rangearray(N); good_shuffle(data); good_samples.push_back(getscore(data)); } sort(good_samples.begin(), good_samples.end(), std::greater()); vi bad_samples; bad_samples.reserve(sample_size); for (int k = 0; k < sample_size; ++k) { vi data = get_rangearray(N); bad_shuffle(data); bad_samples.push_back(getscore(data)); } sort(bad_samples.begin(), bad_samples.end()); int badcount; for (badcount = 0; badcount < sample_size; ++badcount) { if (bad_samples[badcount] > good_samples[badcount]) break; } fprintf(stderr, "bad chance=%d/%d, cutoff=%d\n", badcount, sample_size, bad_samples[badcount]); return bad_samples[badcount]; } template void solve(int k, T cutoff) { printf("Case #%d: ", k+1); int N1 = getInt(); // empty read if (N != N1) fprintf(stderr, "ERROR\n"); vi data; data.reserve(N); for (int i = 0; i < N; ++i) { data.push_back(getInt()); } T score = getscore(data); if (score > cutoff) printf("BAD\n"); else printf("GOOD\n"); } int main(int argc, char** argv) { random_initialize(); if (argc > 1) { int n = atoi(argv[1]); if (n > 0) monte_carlo_rounds = n; } prepare_freq_array(monte_carlo_rounds); int cutoff = get_cutoff_score(); /* Remove to solve the Google Code Jam data set. int T = getInt(); for (int k = 0; k < T; ++k) solve(k, cutoff); */ fprintf(stderr, "Finished with cutoff = %d.\n", cutoff); return 0; }