Всем привет, у меня вопрос по очень простой задаче из acmp.ru ( Преобразование последовательности — 2 )
Вот таким образом я ее пытался решить:
#include <fstream>
#include <algorithm>
#include <map>
#define LL long long
using namespace std;
fstream in("input.txt"), out("output.txt", ios::out);
int B[105], N, k, mi, mv, i;
map<int, int> A;
int main()
{
in >> N;
for(; in >> k; A[k]++, B[i++] = k)
if(A[k] > mv)
mv = A[k], mi = k;
else
if(A[k] == mv)
mi = min(mi, k);
for(i = 0; i < N; i++)
if(B[i] != mi)
out << B[i] << " ";
if(mv)
for(i = 0; i <= mv; i++)
out << mi << " ";
return 0;
}
Когда у себя на компе тестирую тесты, то выходные данные правильные, а как задачу отправляю на проверку, то сразу ошибка на первом тесте пишет. Не могу понять в чем ошибка.
Может кто-то из вас догадается? Я подозреваю, что где-то за пределы массивы выходу и т.п.
Переписал тот же алгоритм, только еще более извращенее, которое прошла все тесты:
#include <fstream>
#include <algorithm>
#include <map>
#define LL long long
using namespace std;
fstream in("input.txt"), out("output.txt", ios::out);
class Q
{
public:
int value;
int count;
} B[105];
int C[105], N, k, q, i;
map<int, int> A;
int CMP(const Q &a, const Q &b)
{
return a.count > b.count;
}
int CMP_(const Q &a, const Q &b)
{
return a.value < b.value;
}
int main()
{
in >> N;
for(; in >> k; A[k]++, C[i++] = k);
for(i= 0; i < N; i++)
B[i].value = C[i], B[i].count = A[C[i]];
sort(B, B + N, CMP);
sort(B, B + B[0].count, CMP_);
for(i = 0; i < N; i++)
if(C[i] != B[0].value)
out << C[i] << " ";
for(i = 0; i < B[0].count; i++)
out << B[0].value << " ";
return 0;
}
Я отправил свое решение которое взяло ACCEPTED, на этот раз оно получило WA1. В состояний проверки все решения получают WA1. Вся проблема в проверочной системе.
Я исправил решение, вот работающий пример:
Тесты этой задачи она прошла на ура.
Там есть еще одна задача, абсолютно такая же, только входные данные могут быть больше.
Преобразование последовательности
Алгоритм выдает TL на 8 тесте.
Я не могу понять, что в моем решении так замедляет алгоритм?
Просто идет чтение из массива, и сразу же находиться числа которые встречаются максимальное количество раз.
Далее просто вывожу массив и все.
Может не стоит эти проверки при чтении из файла делать?
В обсуждениях задачи смотрел, там некоторые даже сортировку использовали...
Подскажите кто-нибудь пожалуйста в чем проблема?
UPD: если использовать сортировку, то сложность будет O(logN * N), а у меня тут просто линейная сложность... Я попробовал проверку за цикл чтения из файла вывести:
Не помогло, тоже самое..
Аааа господа, подскажите пожалуйста..
Не линейная. map<int, int> работает за логарифм (с константой). Именно из-за этого и TL-ится. Сначала замени cin / cout на scanf() / print(). Убери map<int, int> и вместо него сделай обычный массив. Но так как числа могут быть отрицательными, к ним еще надо прибавить 10^6 (таким образом все числа будут от 0 до 2 * 10^6).
Код будет примерно таким:
Седевая моя голова..
У меня же массив "B" из 105 элементов.. Поставил B[200005] и уже TL на 18 ...
Спасибо большое, не додумался бы до такого с массивом для отрицательных элементов..
Сейчас попробую реализовать..
Хотел бы узнать, что делали, если бы элементы были < |10^9| ?
Если бы элементы были бы до 10^9, то я бы отсортировал, и в отсортированном массиве находил бы число которое встречается макс. количество раз.
Код такой примерно:
Попробуйте printf/scanf вместо потоков