Блог пользователя SPyofgame

Автор SPyofgame, история, 4 года назад, По-английски

I am wondering if I could always replace all long long type into int64_t type without breaking the program ? Will it somehow affects the program or remains the same ?

And how about the relationship between int and int32_t types

Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

Автор SPyofgame, история, 4 года назад, По-английски

Recently while I am solving a problem, I realised that increase iterator after erasing the last element of the map (the map is empty) then it would run infinitively

So I stop the loop by adding a small line to check whether it is empty or not

/// map-looping using either iterator or reverse iterator
{
    /// some code upper that erase the element but possible to make the map empty
    if (map.empty()) break;
}

Is there an alternative way (some other implementations) to prevent from iterator increament when the map is empty (and reverse_iterator too if possible)

Полный текст и комментарии »

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

Автор SPyofgame, история, 4 года назад, По-английски

Given two number n and q where 1 ≤ n, q ≤ 10.000

There are n nodes, each node have a green string connect to another. Each 2 node only have 1 string connect between them. There are n * (n — 1) * (n — 2) / 6 total string

You have to answer q queries, each query give 2 number u and v. You paint the string connect (u, v) by color red if they are green, and green if they are red (red <-> green). Then you have to count the number of triangle ABC (1 ≤ A, B, C ≤ n) where (A, B), (B, C), (C, A) have same color (all are red or green).

Time limit for the problem is 1s

Memory limit for the problem is 256Mb

Here are examples

Example 1
Example 2
Example 3

Notice that the number of valid triangle can be bigger than 10 ^ 9

I think the problem can be solved using map

My brute-force approach give 50% points
Update: Solution

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор SPyofgame, история, 4 года назад, По-английски

In this problem. How can I solve it using dsu ?

I see the problem has dsu-tag, but the editorial but doesnt show dsu approach there :(

Have this the code already dsu ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

Автор SPyofgame, история, 4 года назад, По-английски

Are there any effeciency algorithms to find shortest path using disjoin-set data structure ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор SPyofgame, история, 4 года назад, По-английски

I know I am a low-ranker contestant. But during the contest, it took me more than 2 minutes just to do something. And every 30 minutes I been logged out and it take me again 3 ~ 5 minutes to log-in. It is very annoy :( Please help me, why the codeforces was so slow. This is the second time I write this blog (The first was ignore by auto-log-out)

Полный текст и комментарии »

  • Проголосовать: нравится
  • +66
  • Проголосовать: не нравится

Автор SPyofgame, история, 4 года назад, По-английски

Nice logo Codeforces UwU Love it <3

Полный текст и комментарии »

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

Автор SPyofgame, история, 5 лет назад, По-английски

----------

Purpose:

  • First, sorry for my bad English.
  • Second, I know there are lots of topics about this. But after solving a problem that need FastIO, I feel interested in FastIO and decide to do the implementations and comparing them. But it maybe time-consuming so I make this post for ones who maybe try to find the Effeciency-Simple-IO, so you can save time instead of searching more.
  • Third, usually it is need not to use FastIO. In the contest, they usually have twice or more time of the solutions code than the given time limitation. Dont worry about faster IO if it is not needed, you should improve your algorithms first, maybe you can use Bitwise Operations for x8 x32 x64 faster.
  • Fourth, if the problem need to be solve in O(n) ~ O(n log n), and your algorithms work in O(n ^ 2), this Micro-Optimization doesnt help you at all (maybe you will get some more points but hard get AC), you should change the algorithms for further approach.
  • Final, for some problems that needed to be solved by FastIO, you can use the suitable template and modify it for your solving the problem. Dont use the template if you dont really know how to use (I may add a guide path to the post in the future)
  • Conclusion, this post is about comparing the implementations for each version of C++ language and you should choose the most suitable for you.

Here are some implementations to output numbers I found

Time to write first 10.000.000 non-negative numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Time to write 1.000 times first 10000 numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Time to write first 10.000.000 non-positive numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Single Line Template

Putchar Non-recursive toString Implementation
Putchar Non-recursive Dividing Implementation
Putchar Reverse Implementation
Putchar Recursive Implementation
Unlocked-Putchar Non-recursive toString Implementation
Unlocked-Putchar Non-recursive Dividing Implementation
Unlocked-Putchar Reverse Implementation
Unlocked-Putchar Recursive Implementation
Printf Implementation
synchronized(off) Implementation
synchronized(true) Implementation
Cout Implementation
fwrite buffer Implementation

----------

About:

----------

Similiar Topic:

----------

Planning:

  • Test about random 10.000.000 big numbers
  • Test about 10.000.000 numbers 2 ^ k, k integer
  • More implementations (Actually the post is about Faster and Faster Short Output Implementation but I will add some for speed comparing)
  • New output types (long long, double, string)

Полный текст и комментарии »

  • Проголосовать: нравится
  • +62
  • Проголосовать: не нравится

Автор SPyofgame, история, 5 лет назад, По-английски

I dont know how to use Template for multiple input. Can you help me ?

Fast Input Code

Sorry for my bad English. Correct me if I am wrong.

Thanks for reading <3

Полный текст и комментарии »

  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

Автор SPyofgame, история, 5 лет назад, По-английски

I recently found the opperator co_await and co_yield in C++. How should I apply this into the code and should I use these operator in competitive programming ?

Sorry for my bad English and knowledge.

If I am wrong about something please guide me.

Thanks for reading <3

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор SPyofgame, история, 5 лет назад, По-английски

Question: Given two positive numbers N and M, find minimal |c — M| where N mod c = 0

Can we solve this problem in O(log (n)) or faster ?

Here is my approach in O(sqrt(n))

My code

Sorry for my bad English ;-;

If I have wrong something, please tell me. It is better to do that than just downvote me because I and someone will learn many new things <3

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится