-6

I tried submitting my code on cses but every-time the time limit exceeds for last test. I tried using scanf and printf instead but of no use plz help me ..

It basically counts the number of distinct numbers in an array. here is the task

Here is my code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    cin >> n;

    unordered_set<ll> a;

    for(ll i=0; i\<n; i++) {
        ll num;
        cin >> num;
        a.insert(num);
    }
    cout << a.size() << "\n";
    return 0;
}
UpAndAdam
  • 4,515
  • 3
  • 28
  • 46
Dhruv Koli
  • 13
  • 7
    Side notes: (1) [#include ](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) (2) [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) (3) [#define ll long long](https://stackoverflow.com/questions/67649609/using-preprocessing-directive-define-for-long-long) – wohlstad Aug 31 '23 at 10:28
  • 5
    I really wish those competitive coding questions would go away, so first learn C++ and stop blindly copying junk code from others. Remove this `ios_base::sync_with_stdio(false); cin.tie(NULL);` It is rumoured this might gain you time, but no not really (maybe a millisecond in some cases) but it will be less then the timing accuracy of your competitive coding site. The only thing that really matters is the correct algorithm and to avoid unecessary copied. – Pepijn Kramer Aug 31 '23 at 10:30
  • 2
    Learn C++ from : [a recent C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or from [learncpp.com](https://www.learncpp.com/) that site is decent and pretty up to date. Then use [cppreference](https://en.cppreference.com/w/) for reference material (and examples). When you have done all that keep using [C++ core guidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) to keep up to date with the latest best practices since C++ keeps evolving. – Pepijn Kramer Aug 31 '23 at 10:31
  • Make sure you read the guidelines on the C++ tag too (https://stackoverflow.com/tags/c%2B%2B/info#:~:text=c%2B%2B-,Tag%20usage,-When%20posting%20questions) – Pepijn Kramer Aug 31 '23 at 10:35
  • 3
    Try to use simply an std::vector with capacity reserved to n. Then just look up if the number is in or not, if it is just push_back and then return its size. This will make only one allocation in the whole run. Depending on the unique number count it should beat unordered_set up to some length which is a different problem. But for a few numbers it should be much faster. Also as others wrote. Remove the unnecessary crap and trust your compiler. Usually it is much cleverer in simple tasks than the programmer... – simre Aug 31 '23 at 10:36
  • 2
    I would say the choice of the `long long` type is a mistake, it is not needed anywhere for this problem, and unnecessary consumes space and time. Read the code challenge constraints and carefully pick the suitable data type (see [cppreference](https://en.cppreference.com/w/cpp/language/types)) – trincot Aug 31 '23 at 10:45
  • 1
    Adding `a.reserve(n);` right before the loop to prevent rehashing in the middle, changing all `ll` to `int`, replace `#include ` by the 2 files you really need and remove the io sync stuff, should do the job. – mch Aug 31 '23 at 11:13
  • 1
    @PepijnKramer I actually had run into TLE issues and was unable to solve a HackerRank problem until I did `ios_base::sync_with_stdio(false)`. It's stupid, but it actually makes a big difference. – Jan Schultke Aug 31 '23 at 12:19
  • @JanSchultke There are always exceptions ;) – Pepijn Kramer Aug 31 '23 at 12:30
  • It is known that this particular test has been designed to defeat unordered_set. – Matt Timmermans Aug 31 '23 at 13:06
  • maybe its just I am stuck with old C++ but what the heck is `\<` operator ? in the `for(ll i=0; i\ – Spektre Sep 02 '23 at 05:56

2 Answers2

0

In normal situations, this code is quick enough to pass all data points, because the time complexity is O(n). If this data cannot get "Accepted", I have two advice:

  1. Use int instead of long long
  2. Use "set" instead of "unordered_set"(In some time, unordered_set is possible to be hacked by specially constructed data)
ForLight
  • 42
  • 4
0
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    // 0
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // 1
    int n;
    std::cin >> n;
    int i, tmp;
    std::vector<int> seq;
    // allocate space for at least n elements
    seq.reserve(n);
    for (i = 0; i != n; ++i) {
        std::cin >> tmp;
        seq.emplace_back(tmp);
    }
    // 2
    // sort seq in non-descending order so you can find the duplicates
    std::sort(seq.begin(), seq.end());
    // 3
    // unique reorders the input range so that each integer appears once in the 
    // front portion of the range and returns an iterator one past the unique range
    auto end{ std::unique(seq.begin(), seq.end()) };
    // 4
    // ans = end - seq.cbegin()
    auto ans{ std::distance(seq.begin(), end) };
    std::cout << ans << '\n';
    return 0;
}
Petar Ivanov
  • 73
  • 6