MMMim's blog

By MMMim, history, 8 days ago, In English,

Is this problem 1351C - Skier can be solved without stl(map/pair/set in cpp)? If it is then how?

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it +13 Vote: I do not like it

A map makes it so easy, what would be the point of solving it without one?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I don't know how to implement map

    so

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      The whole point of it being a standard template library is that you don't have to implement it yourself; you just need to learn how to use it.

      I recommend investing a little bit of time to familiarize yourself with common tools that you are definitely going to need in order to be any good (such as maps/pairs/sets/vectors) before spending too much time worrying about which problems you can solve.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah. Feel to implement red — black tree or treap

»
8 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Being afraid of using any structures at all is a very bad plan that will hinder your progress. However, to answer your question:

yes it is possible to solve it without those things. You can make a list of all positions you visit during your ski trip. Each position has an x and y coordinate. You can store these into the first 32 bits and last 32 bits of a long long, so now you just have an array of long longs and you need to know how many unique numbers are in this array. If you sort the array with std::sort, then you can iterate through it and count how many times it changes. The first time you hit each new number (or equivalently, each new space) you have to pay 5 time units. Every future time you have to pay only 1 time unit.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Yea. You can struct your own data type and then solve it if you don't know how to use stl. If you wanna learn how to use stl, you can read this article(In Bangla). http://www.progkriya.org/gyan/stl.html