読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 11321 : Sort! Sort!! And Sort!!!

問題リンク:

問題概要:
n個の要素 a[i]( 0 <= i < n )とMが与えられる
a[i]を以下の条件に従ってソートする
・a[i] % M の値が小さい順にソートする
・a[i] % M の値が同じ場合
 ・a[i]とa[j]の片方が偶数で片方が奇数ならば奇数を先にする
 ・a[i]とa[j]の両方が偶数なら小さい順にする
 ・a[i]とa[j]の両方が奇数なら大きい順にする

解法:
その通りに実装する
偶数か奇数か判定する際に、
%を使う場合は絶対値をとったほうが良い、、(-1対策)
それか&1をとると良い

コード:

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int N,M;

struct P
{
  int value;
  P(int value=INT_MAX):value(value){}
  bool operator < (const P& a)const
  {
    if(value%M != a.value%M)
      {
	return value%M < a.value%M;
      }
    if((value&1) != (a.value&1))
      {
	return (value&1) > (a.value&1);
      }
    if(value&1)
      {
	return value > a.value;
      }
    return value < a.value;
  }
};

int main()
{
  while(1)
    {
      cin >> N >> M;
      cout << N << " " << M << endl;
      if(!(N|M))break;
      vector<P> vec(N);
      rep(i,N)cin >> vec[i].value;
      sort(vec.begin(),vec.end());
      rep(i,N)cout << vec[i].value << endl;
    }
  return 0;
}