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](http://mirror.codeforces.com/contest/1077/problem/D) ↵
↵
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.↵
↵
↵
↵
↵
[Problem link](http://mirror.codeforces.com/contest/1077/problem/D) ↵
↵
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.↵
↵
↵
↵
