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

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

when i wrote the code using small to larger techinque,

if i write code like

	if((int)s.size()<(int)s1.size()){
		for(set<pair<lld,int> >::iterator it = s.begin();it!=s.end();it++) s1.insert(*it);
		s = s1;
	}else{
		for(set<pair<lld,int> >::iterator it = s1.begin();it!=s1.end();it++) s.insert(*it);
	}

it gets TLE ( problem accept 4 second )

but if i write code like

	if((int)s.size()<(int)s1.size()){
		for(set<pair<lld,int> >::iterator it = s.begin();it!=s.end();it++) s1.insert(*it);
	        swap(s,s1);
	}else{
		for(set<pair<lld,int> >::iterator it = s1.begin();it!=s1.end();it++) s.insert(*it);
	}

it gets AC and run so fast ( runnging time is 200ms )

but i don't know why difference of time is so big.. help..

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Auto comment: topic has been updated by TaeHo0o00o0N (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

swap for set is O(1): http://www.cplusplus.com/reference/set/set/swap-free/

internal pointers are exchanged, that's why.

Also, your snippets do different things.

»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

The correct way to do it is

s=move(s1);

The reason swap and move work in O(1) for all STL containers is because the content doesn't have to be duplicated unlike in s=s1.

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

While original question is already answered, why don't you write this snippet as

if (s.size() < s1.size()) { //I understand why you used cast to int, but here it's useless. And easier to use macros/function SZ, which casts to int
    for (auto& x: s)
        s1.insert(x);
    s = move(s1);
}
else {
    for (auto& x: s1)
        s.insert(x);
}

I tried to read your code from my phone and it took me more than one minute to understand what it means. Use c++17 whenever you can, it really increases readability. (But this one trick is even since c++11)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Thank you for advising for me!! I agree what you are saying... but i'm too lazy to correct my disadvantage.. Try to use macro and increase my readability