gcj-distribution-fitting.cpp

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<time.h>
using namespace std;

int w[1001],   // instance of vector for creating distribution
C[1001][1001], // histograms per output bucket
O[1001];       // an "output," used only for inputting lines
bool v[1001];  // ordered good/bad bools

struct A{
	int ord,  // testcase number
R;                // Sum of histogram buckets over each index+value
	bool operator <(const A &p)const{
		return R < p.R;
	}
}p[1000];

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int i, TC, T, n, j;

// take 30 M trials to fill out histogram
	srand((unsigned)time(NULL));
	for (i = 0; i < 3000000; i++){
		for (j = 0; j < 1000; j++){
			w[j] = j;
		}
		for (j = 0; j < 1000; j++){
			swap(w[j], w[rand() % 1000]);
		}
		for (j = 0; j < 1000; j++){
			C[j][w[j]]++;
		}
	}

	scanf("%d", &TC);
	for (T = 1; T <= TC; T++){
		scanf("%d", &n);

// set test case number
		p[T].ord = T;
		for (i = 0; i < n; i++){
			scanf("%d", &O[i]);

// sum histogram weight for this value for this index
			p[T].R += C[i][O[i]];
		}
	}

// lowest summed weights first
	sort(p + 1, p + TC + 1);

// call the first half "GOOD"
	for (i = 1; i <= 60; i++)v[p[i].ord] = true;
	for (i = 1; i <= TC; i++){
		printf("Case #%d: ", i);
		if (v[i])printf("GOOD\n");
		else printf("BAD\n");
	}
}