Well, if I understand your alternate spec, you'll accept a routine that takes an original array @a and produces two arrays holding the elements for which c() is false and the elements for which c() is true respectively. The following produces two array refs with 33 chars in the body S:

my @a = (0 .. 25);
sub c{$_[0] % 3 == 0 }
sub S{my@t;push@{$t[c($_)]},$_ for@_;@t}
my($l,$r)=S(@a);
print "@$l\n";
print "@$r\n";
[download]

Following tye's lead of passing in a ref to c(), it grows to 43 chars:

my @a = (0 .. 25);
sub c{$_[0] % 3 == 0 }
sub S{my@t;push@{$t[$_[0]($_)]},$_ for@{$_[1]};@t}
my($l,$r)=S(\&c,\@a);
print "@$l\n";
print "@$r\n";
[download]

Note, the sub deref in that one (sans ->) requires 5.6+