It depends on the song, and on the contest rules. One example is “Hard Day’s Night”, which a Beatles fan can positively identify in a tiny fraction of a second - it’s not even necessary to hear all of the first note. But that’s because of the unique sound of the particular instruments playing the first note, and the overall sound of the recording. Change the contest rules so that every example is played with bland computer-generated tones, or even played on brand-new recordings all made by the same skilled-but-bland cover band, and the same example becomes much more difficult.
In short, are you recognizing the song? Or are you recognizing the band, the recording studio, the marginally out-of-tune and very recognizable piano they used that day, and so on?