You need a Pokemon that knows Rock Smash for this route. You'll find the Winstrate's House along the way, shortly after leaving Mauville City. They're a battle-obsessed family, and you can take their challenge to fight five battles in a row.
Victor (Reward: p1,216)
Victoria (Reward: p1,280)
Vivi (Reward: p256)
Vicky (Reward: p1,760)
After defeating them all, head inside their house and talk to the mother to receive a Macho Brace. Now leave the house and continue north. Smash the rocks blocking the path and continue forward.
You'll find a reporter and a camera man on the right side of the main path. If you defeat them in battle, they'll ask you if you can be interviewed.
Interviewers Gabby and Ty (Reward: p1,600)
Picnicker Irene (Reward: p288)
Continue north and you'll find a split in the road. You won't be able to continue north in the route's desert area because of the vicious sandstorm that's happening. To continue with the story, you have to turn left to reach Route 112.
Camper Travis (Reward: p304)
Backpacker Emory (Reward: 504)
If you rocksmash the first rock on the very left you'll find a heart scale!
How do I get through the "vicious" sandstorm on Route 111 in Pokémon Alpha Sapphire and or Pokémon Omega Ruby?