torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #150, Division 2, A : Dividing Orange

概要

n * k 個の部分に分割されたオレンジがある。
k 人の子供がおり、それぞれが欲しい部分の番号を一つ持っている。
欲しい部分の情報は数列 a として与えられる。
以下の条件を満たしつつオレンジを配分した場合の配り方を一つ出力せよ。

  • 各子供に n 個の部分を配分する
  • i 番目の子供は a_i 番の部分を含むように配分される
  • 同じ部分が複数の子供に配分されることはない

解法

a に含まれない番号は自由に使えるので、各子供に a_i を振り分けたあと、そこから適当に配る。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, k;
	cin >> n >> k;

	VI as( k );

	EACH( a, as )
	{
		cin >> a;
	}

	vector<bool> used( n * k + 1 );

	REP( i, 0, as.size() )
	{
		used[ as[i] ] = true;
	}

	int idx = 1;

	REP( i, 0, as.size() )
	{
		cout << as[i];

		REP( j, 0, n - 1 )
		{
			while ( used[ idx ] )
			{
				idx++;
			}

			cout << ' ' << idx++;
		}

		cout << endl;
	}

	return 0;
}