Loading...

Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.

nsnikolova1 avatar nsnikolova1 3 Точки

Visitors c++ недостиг на време

Здравейте!

Последните тестове в джъдж дават недостатъчно време.Предварително се извинявам, но нещо не мога да  се оправя с линковете.

Задачата е :

Task 4 – Visitors (JA4-Task-4-Visitors)

Some fictional website tracks visitors by assigning them an id, and getting their name and age. Visitors can have matching names or ages, but will always have unique ids. Multiple records of a visit with the same id mean the user has visited the website multiple times.

The website supports the following operations for tracking and querying the tracked items:

- Adding a visit entry to the database. 
Syntax: entry [id] [name] [age]. //Стойности в БД 
Executed when user visits the website. id and name are strings, and age is a positive integer number between 1 and 99. Note: most of these operations will be duplicates, because visitors to the website are likely to visit again, in which case the id, name and age values will be the same.
Example: entry 1A John 15

- Querying the number of visitors with a certain name. 
Syntax: name nameValue.  /Посетители по име
Counts the number of unique visitors which have been entered in the database with the specified name, when the query was given.
Example:
entry 1A John 15
entry 1B Tony 16
entry 1A John 15
entry 1C John 86
name John – result should be 2 (There are 2 visitors named “John” – with ids 1A and 1C)

- Querying the number of visitors within a certain age range. 
Syntax: age startAge endAge.  //Възрастов диапазон
Counts the number of unique visitors which have been entered in the database when the query was given, having an age between startAge (inclusive) and endAge (exclusive).
Example:
entry 1A John 15
entry 1B Tony 16
entry 1A John 15
entry 1C Jebediah 87
entry 1D Mark 16
age 15 87 – result should be 3 (Mark, John and Tony are in the range)

- Ending the operations. 
Syntax: end. 
Stops the program.

Write a program which supports the operations as described above.

Input

Two or more lines containing operations as described above. The last line always contains end.

Output

A single line per each query command (age or name) in the input, containing a single integer number – the result of the query.

Restrictions

There will be no more than 20000 lines (operations) in the input. 

Ages are between 1 (inclusive) and 100 (exclusive). Names are strings of English letters (a-z, A-Z), have a length less than 20 letters and the maximum number of unique visitor names in the input is less than 40. Ids are strings of English letters and digits (a-z, A-Z, 0-9) and tend to (not guaranteed) represent hexadecimal numbers. Ids are no more than 4 symbols long.

entry operations which have the same id will also have the same name and age.

The total running time of your program should be no more than 0.5s

The total memory allowed for use by your program is 16MB.

Example I/O

Example Input

Expected Output

Explanation

entry 1A John 15

entry 1B Tony 16

entry 1A John 15

entry 1C John 86

name John

name Jebediah

entry 1A John 15

entry 1B Tony 16

entry 1A John 15

entry 1E Jebediah 87

entry 1D Mark 16

age 15 87

end

2

0

4

When the “name John” operation is done, there are 2 unique visitors named John.

When the “name Jebediah” operation is done, no visitor with the name Jebediah has been entered (yet).

When the “age 15 87” operation is done, the 2 Johns (15 and 86 years old), Tony (16 years old) and Mark (16 years old) are the results.

 

Решението:

    string id, name, word, input, nameValue;
    int age, countAge=0, startAge, endAge, countName = 0;
    istringstream line; 
    unordered_map <string, string> UserName;
    map <string, int> UserAge;
  
 
    //funkcia za proverka ime
    void SearchName(string nameValue, unordered_map<string,string> UserName)
    {
        
        for (auto it = UserName.begin();it!= UserName.end(); it++)
        {
            if (it->second == nameValue)
            {
                countName++;
                
            }
            
        }

        if (countName != 0)
        {
        cout<<countName<<endl;
        }
        else
        {
            cout << "0" << endl;
        }

        countName = 0;

    }

    //proverka vyzrastov diapazon
    //age startAge endAge.
    void Countage(int startAge,int endAge, map <string, int> UserAge)
    {
        
        for ( auto it = UserAge.begin();it!= UserAge.end(); it++)
        {
            if ((startAge<=it->second) && (it->second < endAge))
            {
                countAge++;
                
            }
        }
        if (countAge != 0)
        {
            cout << countAge << endl;
        }
        else
        {
            cout << "0" << endl;
        }
        countAge = 0;
    }

    


int main()
{
     while (true)
    {
    
        getline(cin, input);
        istringstream line(input);
        line >> word;
            if (word == "entry")
            {
                
                    line >> id;
                    line >> name;
                    line >> age;
                   
                    UserName.emplace(make_pair(id, name));
                    
                    UserAge.emplace(make_pair(id, age));
           
            }
            
            if (word == "name")
            {
                line >> nameValue;
                SearchName(nameValue,UserName);
            }
            
            if (word == "age")
            {
                line >> startAge;
                line >> endAge;
                Countage(startAge,endAge,UserAge);
            }
            
            if (word == "end")
            {
                break;
            }

        
    }
}

Ако може да поясните как джъдж определя времето

0
Open Courses
MartinBG avatar MartinBG 4803 Точки

Логически решението е вярно, но в кода има някои лоши практики (напр. глобални променливи, функции, които правят повече от едно нещо, създаване и предаване на копия като аргументи към функциите). 

Това е решението, с поправени сигнаури на функциите (използване на глобалните променливи, а не подаване на техни копия при всяко извикване) и няколко оптимизация за работа с входно-изходните потоци - минява за 0.270 сек в Judge.

 

А това е версия, без глобални променливи и функции със само едно предназначение - минава в Judge за около 0.330 секунди:

#include <iostream>
#include <sstream>
#include <unordered_map>
#include <map>

using namespace std;

int countByName(const string& nameValue, const unordered_map<string, string>& UserName) {
  int countName = 0;
  for (const auto& it : UserName) {
    if (it.second == nameValue) {
      countName++;
    }
  }
  return countName;
}

int countByAge(int startAge, int endAge, const map<string, int>& UserAge) {
  int countAge = 0;
  for (const auto& it : UserAge) {
    if ((startAge <= it.second) && (it.second < endAge)) {
      countAge++;
    }
  }
  return countAge;
}

int main() {
  std::ios_base::sync_with_stdio(false); //io optimization
  std::cin.tie(nullptr); //io optimization

  unordered_map<string, string> userName;
  map<string, int> userAge;

  string input;
  while (getline(cin, input) && input != "end") { // faster
    istringstream iss(input);
    string command;
    iss >> command;

    if (command == "entry") {
      string id, name;
      int age;
      iss >> id >> name >> age;
      userName.emplace(id, name);
      userAge.emplace(id, age);
    } else if (command == "name") {
      string nameValue;
      iss >> nameValue;
      int count = countByName(nameValue, userName);
      cout << count << endl;
    } else if (command == "age") {
      int startAge, endAge;
      iss >> startAge >> endAge;
      int count = countByAge(startAge, endAge, userAge);
      cout << count << endl;
    }
  }
}

 

Ето и няколко алтернативни решения на задачата:

- линк 0.115 сек

- линк 0.100 сек 

- линк 0.015 сек

0
14/05/2020 15:14:14
nsnikolova1 avatar nsnikolova1 3 Точки

Много полезно.Благодаря!

1
productxbest avatar productxbest 0 Точки

This microwave oven has 211 Indian automobile-prepare dinner menu options. Hence, it's far an all-purpose microwave oven. Here are some of its first-rate capabilities. best microwave oven in india Diet Fry function enables you to put together your preferred fried eatables like samosas, pakoras, and others with a minimal quantity of oil with out compromising at the taste aspect.This oven is able to baking twelve one of a kind kinds of rotis like Naans, Kulchas, Parathas, Lachchas, Tandoori rotis, Rumali rotis, and so forth at one touch of a button.

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.