simp1eton's blog

By simp1eton, 14 years ago, In English
Hi all,

I have this really weird bug with STL set that I cannot understand.

My set function is given below.

struct pt{int a,b,node;}tmp,ins;
struct cmp{
    bool operator()(pt a, pt b){
        if(ans[a.node] != ans[b.node]) return ans[a.node] < ans[b.node];
        if(a.node != b.node) return a.node<b.node;
        if(a.a != b.a) return a.a<b.a;
        return a.b<b.b;
    }
};
set <pt,cmp> pq;

I am using this modified set for running dijkstra algorithm. However, I got some infinite loop somewhere. When I ran some debugging output, I noticed something extremely weird.

//Code portion with bug

while(!pq.empty()){
       tmp = *pq.begin();
       pq.erase(tmp);
      printf("removed %d %d %d\n", tmp.node, tmp.a, tmp.b);  //This node is removed.
       if(pq.find(tmp) == pq.end()) printf("erased\n");    //This line is printed, which means the element is removed
       printf("first element is now %d %d %d\n", pq.begin()->node, pq.begin()->a, pq.begin()->b);
               //Amazingly, the first element is exactly the same as tmp! And I thought I already deleted it and cannot find it in the set...
}

Can someone tell me what is wrong? Is there something wrong with my comparison function or something that leads to the bug?

Thanks in advance.

Full text and comments »

Tags gcj
  • Vote: I like it
  • 0
  • Vote: I do not like it

By simp1eton, 14 years ago, In English
Hi,

I am new to Codeforce. Hello everyone!

I just coded for A - Threatre Square from Beta Round #1 and got the following error. Can someone tell me why?

The first problem is - I cannot use scanf and printf when I use #include <iostream>

The second problem is - Why is it that the first code does not work while the second one does?

First Code:
#include <iostream>
#include <cstdio>
using namespace std;

long long int N,M,A;

int main(){
    scanf("%lld%lld%lld", &N,&M,&A);
    printf("%lld\n", ((N+A-1ll)/A)*((M+A-1ll)/A));
}

// The first code failed at test case 16.

Second Code:
#include <iostream>
#include <cstdio>
using namespace std;

long long int N,M,A;

int main(){
    cin>>N>>M>>A;       //The only thing I did is to change all scanf and printf into cin and cout
    cout<<((N+A-1)/A)*((M+A-1)/A)<<endl;
}

//The second code passed all testcases.

Thanks a lot in advance.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it