ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1196. History Exam

what is my problen on wa2?? on c++
Posted by nick nikuradze 19 Apr 2016 00:22
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int N,M,a,b;
    vector <int> t;
    vector <int> s;
    vector <int> st;
    cin>>N;
    for(int i=0; i<N; i++)
    {
        cin>>a;
        t.push_back(a);
    }
    cin>>M;
    for(int i=0; i<M; i++)
    {
        cin>>b;
        s.push_back(b);
    }
    for(int i=0; i<M; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(s[i]==t[j])  st.push_back(s[i]);
        }
    }
    sort(st.begin(),st.end());
    cout<<st.size();
    return 0;
}
Re: what is my problen on wa2?? on c++
Posted by ToadMonster 19 Apr 2016 13:28
"Professor's list is sorted in non-descending order", so duplicates allowed.
You are pushing s[i] into out not once but as many times as equal numbers found in t.
Break internal cycle when first equality found.

But. After I fixed your code I received TLE 8 because of "N*M" complexity.
You must optimize perfomance (and should - memory usage).
Re: what is my problen on wa2?? on c++
Posted by nick nikuradze 20 Apr 2016 12:58

Edited by author 20.04.2016 13:21

Edited by author 20.04.2016 13:21
Re: what is my problen on wa2?? on c++
Posted by nick nikuradze 20 Apr 2016 13:22
but what can i do to solve TLE8
Re: what is my problen on wa2?? on c++
Posted by ToadMonster 20 Apr 2016 21:53
C.O. thinks you should optimize your program.

1) Remove s and st arrays. You can - read students value, check it, increase counter if necessary.

2) Speed up checking if date is in professor dates. You can use binary search over sorted array, std::set, std::unordered_set for example.
Re: what is my problen on wa2?? on c++
Posted by nick nikuradze 22 Apr 2016 13:23
Now I have this code but I have compilation eror why?
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
    int N,M,a,b,counter=0;
    vector <int> t;
    set <int> s;
    cin>>N;
    for(int i=0; i<N; i++)
    {
        cin>>a;
        t.push_back(a);
    }
    cin>>M;
    for(int i=0; i<M; i++)
    {
        cin>>b;
        s.insert(b);
    }
    for(int i=0; i<s.size(); i++)
    {
        for(int j=0; j<t.size(); j++)
        {
            if(s[i])==t[j])  {counter++; break;}
        }
    }

    cout<<counter;
    return 0;
}