Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

shnoh's blog

By shnoh, history, 3 weeks ago, In English,

On the round #521 (Div.3), I tried to solve the question using the following code but it fails the test on simple example (Wrong answer on test 39). It runs correctly on my computer. Can anybody tell me why this happens? I am working on it but still did not get the answer.

Problem link

Example

2 2

1 1

My output (on the server)

1 5301

Answer (and also my output on my computer)

1 1

Diagnostics

Diagnostics detected issues [cpp.clang++-diagnose]: C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\vector:1802:11: runtime error: pointer index expression with base 0x12c00210 overflowed to 0x9fdfd8b0 SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\vector:1802:11 in

Source code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

void find(int lower, int upper, int k, vector<pair<int, int> > counts);
bool check(int num, int k, vector<pair<int, int> > counts);

int main()
{
	ios_base::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	map<int, int> m;
	for (int i = 0; i < n; ++i) {
		int val;
		cin >> val;
		++m[val];
	}

	vector<pair<int, int> > counts;

	for (map<int, int>::const_iterator iter = m.begin();
		 iter != m.end(); ++iter) {
		pair<int, int> instance;
		instance.first = iter->second;
		instance.second = iter->first;
		counts.push_back(instance);
	}

	sort(counts.begin(), counts.end());
	reverse(counts.begin(), counts.end());

	find(1, n/k+1, k, counts);
	cout << "\n";

	return 0;
}

void find(int lower, int upper, int k, vector<pair<int, int> > counts) {
	if (upper == lower) {
		int i = 0;
		while (k > 0) {
			int repeat = counts[i].first/upper;

			if (k - repeat < 0) 
				for (int j = 0; j < k; ++j) 
					cout << counts[i].second << " ";
			else
				for (int j = 0; j < repeat; ++j) 
					cout << counts[i].second << " ";

			k -= repeat;
			++i;
		}
		return;
	}

	int mid = (upper + lower) / 2 + 1;

	if (check(mid, k, counts))
		find(mid, upper, k, counts);
	else
		find(lower, mid-1, k, counts);
}

bool check(int num, int k, vector<pair<int, int> > counts) {
	int cnt = 0;
	int i;
	while (k > 0) {
		if (counts[i].first < num) break;

		int repeat = counts[i].first/num;
		k -= repeat;
		++i;
	}
	if (k <= 0) return true;
	else return false;
}

I know my answer is not optimal, but still want to figure out what happened on my answer.

 
 
 
 

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shnoh (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shnoh (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shnoh (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

You did not initiate the variable i in function check with 0. Also, you should put a verification in the while of this same function besides the k > 0 one: i < (int) counts.size().