0

What makes the first code faster than the second? I tried those 2 codes one gave me a Time limit that exceeded 1000 ms and the other works on 140ms at a long test input of CodeForces test

#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int n, m, a, l, r, c(0), d(0);
scanf("%d%d", &n, &m);
while (n--)
{
    scanf("%d", &a);
    if (a == 1)
    {
        c += 1;
    }
    else
    {
        d += 1;
    }
}
int up = min(c, d) * 2;
while (m--)
{
    scanf("%d%d", &l, &r);
    printf((r - l) % 2 == 1 && r - l < up ? "1\n" : "0\n");
}
return 0;
}

the slow one is:

#include <bits/stdc++.h>
int main()
{
int n, ones{}, _ones{}, l, r, q, temp;
std::cin >> n >> q;
while(n--)
{
    std::cin >> temp;
    if(temp == 1)
        ones++;
    else
        _ones++;
}
int common = std::min(ones, _ones) * 2;
while(q--)
{
    std::cin >> l >> r;
    std::cout << ((r - l) % 2 == 1 && r - l < common ? "1\n" : "0\n");
}
}
Fathy Khalid
  • 1
  • 2
  • 1
    The time complexity is the same, as the algorithm is identical. Now, C++ streams are notably slower than C classical I/O, *especially when the synchronization with C I/O is not turned off*. – prapin Apr 23 '22 at 19:17
  • 2
    Online coding competition sites are no profilers and running a program a single time in an unknown and uncontrollable environment doesn't give meaningfull results. You shouldn't take these numbers too serious. – Lukas-T Apr 23 '22 at 19:19
  • 2
    See [Why should I not #include ?](https://stackoverflow.com/q/31816095). – prapin Apr 23 '22 at 19:25
  • 1
    Try the slow code with `std::ios::sync_with_stdio(false);` added to the start of the program to see if that's an I/O issue. – lisyarus Apr 23 '22 at 19:35
  • Cin and cout weren’t built for speed, they were built for flexibility. Generally speaking you can have one or the other. – Taekahn Apr 23 '22 at 21:19

1 Answers1

-2

I'm not sure if library imports/includes are counted, but doing the #include <bits/stdc++.h> usually takes a lot of time generally

Might be because of that, maybe include only the ones you need

RaderH2O
  • 3
  • 1
  • 1
  • 5
  • 4
    Including `` might slow *compilation* time, but it shouldn't affect *execution* time, which is what the question is about. – lisyarus Apr 23 '22 at 19:34