PKU 1174 Contact

• 制限時間が緩いので全探索を定数レベルで高速化すれば通る

bool compareByConditions(const string& lh, const string& rh) {
	return lh.size() != rh.size() ? lh.size() > rh.size() : lh > rh;
}

string toString(int value, int length) {
	char buffer[1024];
	for (int i = 0; i < length; ++i) {
		buffer[i] = (value & 1) + '0';
		value >>= 1;
	}
	buffer[length] = '\0';
	reverse(buffer, buffer + length);
	return buffer;
}

static char buffer[1024 * 1024 * 3];
int main() {
	int A, B, N;
	scanf("%d%d%d%s", &A, &B, &N, buffer);
	int length = strlen(buffer);
	while (buffer[length - 1] != '2') {
		buffer[--length] = '\0';
	}
	buffer[--length] = '\0';

	hash_map<int, int> counter;
	for (int len = A; len <= B; ++len) {
		int index = 0;
		int value = 0;

		while (index < len - 1 && index < length) {
			value <<= 1;
			value |= (buffer[index++] - '0');
		}

		while (index < length) {
			value <<= 1;
			value |= (buffer[index++] - '0');
			value &= (1 << len) - 1;

			++counter[value | (len << 16)];
		}
	}

	map<int, vector<string> > answer;
	for (hash_map<int, int>::iterator it = counter.begin(), itEnd = counter.end(); it != itEnd; ++it) {
		const int length = (it->first >> 16);
		const int value = (it->first & ((1 << 16) - 1));
		answer[it->second].push_back(toString(value, length));
	}

	int n = 0;
	for (map<int, vector<string> >::reverse_iterator rit = answer.rbegin(); rit != answer.rend() && n < N; ++rit, ++n) {
		sort(rit->second.begin(), rit->second.end(), compareByConditions);

		cout << rit->first;
		for (vector<string>::iterator it = rit->second.begin(), itEnd = rit->second.end(); it != itEnd; ++it) {
			cout << " " << *it;
		}
		cout << endl;
	}
}