-1
\$\begingroup\$

Roy is working on HackerEarth Profile. Right now he is working on User Statistics. One of the statistics data (Code Streak) is as follows:

Given the User Activity Data, find the maximum number of continuous correct solutions submitted by any user. Seems easy eh? Here's the catch! In order to maximize this number a user could have submitted a correct answer to the same problem which he has already solved. Now such cases cannot be tolerated. (See test case for clarification). Also in all the continuous correct submissions multiple correct submissions to same problem should be counted only once.

User Activity Data will be as follows: Total number of submissions by the user - N For each submission its Submission ID - S and Result - R (Solved or Unsolved) will be given. Solved is represented by integer 1 and Unsolved by 0.

Input: First line contains integer T - number of test cases. T test cases follow. First line of each test case will contain N. Next N lines each will contain two space separated integers S and R.

Ouput: For each test case output in a single line the required answer.

Constraints:
1 <= T <= 1000
1 <= N <= 1000000 (10^6)
1 <= S <= 1000000 (10^6)
0 <= R <= 1

Sample Input
3
6
1 0
2 1
3 1
4 1
5 1
6 0
5
1 1
2 0
3 1
1 1
2 1
4
1 1
2 1
2 1
3 1

Sample Output
4
2
3

Problem Link

How to improve this code with more use of advance C++ features and to improve time complexity.

#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
    unsigned int t, n, s, r;

    scanf("%d", &t);
    while (t--) {
        unsigned int count = 0, max_count = 0;
        scanf("%d", &n);
        std::vector<bool> status(1000000, false);

        for (unsigned int i = 0; i < n; ++i) {
            scanf("%d%d", &s, &r);
            if (r == 1 && status[s] == false) {
                count++;
                status[s] = true;
            }
            else if (r == 0) {
                count = 0;
            }
            max_count = std::max(count, max_count);
        }
        printf("%d\n", max_count);
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I don't understand the use of std::vector<bool> status(1000000, false); in your solution at all. How does that help to solve the problem when defined within the while loop? Also hardcoding 1000000 elements looks not right for me. Did your code pass the test cases when submitted? \$\endgroup\$ – πάντα ῥεῖ Oct 18 at 16:22
  • \$\begingroup\$ Yeah, my code submitted successfully for all test cases. \$\endgroup\$ – coder Oct 19 at 3:59
  • \$\begingroup\$ I looked at some of your other questions, you know the proper way to do input and output in C++, why are you using scanf and printf? \$\endgroup\$ – pacmaninbw Oct 19 at 12:53
  • \$\begingroup\$ @pacmaninbw I have read on a codeforces blog that they are fast compared to cin and cout. \$\endgroup\$ – coder Oct 19 at 16:15
  • \$\begingroup\$ Why do you go to competitive programming sites anyway if you want to actually write good C++ code? Learning C++ from "competitive programming" is like learning English from a rap contest. \$\endgroup\$ – L. F. Oct 20 at 7:29
2
\$\begingroup\$

Don't use printf and scanf. They are not faster, sometimes slower, and prone to undefined behavior. Use I/O streams instead. In fact, every single call to printf and scanf in your code is undefined behavior — you are consistently using %d to print unsigned ints.

You can call

std::ios_base::sync_with_stdio(false);

before doing any I/O operation to turn off synchronization with cstdio, making the streams faster.

@pacmaninbw I have read on a codeforces blog that they are fast compared to cin and cout. – coder 16 hours ago

Disregard it. "Competitive programming style C++" is a completely different language than the correct, proper C++. Learning C++ from "competitive programming" is like learning English a rap contest.

\$\endgroup\$
1
\$\begingroup\$

Not sure what you mean by advanced c++ features, but you could use an std::unordered_set to store the submission id.

#include <cstdio>
#include <unordered_set>
#include <algorithm>

int main() {
    unsigned int t, n, s, r;
    std::unordered_set<int> seen;

    scanf("%d", &t);
    while (t--) {
        unsigned int count = 0, max_count = 0;

        seen.clear();

        scanf("%d", &n);

        for (unsigned int i = 0; i < n; ++i) {
            scanf("%d%d", &s, &r);

            if (seen.count(s) == 0) {
                if (r == 1) {
                    count++;
                }
                seen.insert(s);
            }
            if (r == 0) {
                count = 0
            }
            max_count = std::max(count, max_count);
        }
        printf("%d\n", max_count);
    }
}

I'm not at a PC with a C++ compiler, so this hasn't been tested.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.