Codeforces #166, C : Secret

問題文

http://codeforces.com/contest/271/problem/C

概要

1 〜 k までの数字を n 個並べる。
各数字について、そのインデクスからなる単調増加な数列が等差数列になってはいけない。
このような並べ方を一つ示せ。
そのような並べ方が存在しない場合は -1 を印字せよ。

解法

k * 3 が n より大きい場合、二つしか並べられない数字が存在するため、解はありません。
それ以外の場合は解があります。

まず、111222333... のように並べます。
その後、112122 のように、奇数の端と偶数の端を入れ替えます。
ただし、k * 3 が n と等しいく k が奇数である場合、末尾が kkk になってしまうので、全体をひとつ rotate します。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

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

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

	if ( n < k * 3 )
	{
		cout << -1 << endl;
		return 0;
	}

	VI ary( n, k + 1 );

	REP( i, 0, ary.size() )
	{
		ary[i] = i / 3 + 1;
		if ( k < ary[i] )
		{
			ary[i] = 1;
		}
	}
	
	REP( i, 0, ary.size() - 1 )
	{
		if ( ary[i] % 2 && ary[i] != ary[ i + 1 ] )
		{
			swap( ary[i], ary[ i + 1 ] );
			i += 2;
		}
	}

	if ( k % 2 && k * 3 == n )
	{
		rotate( ary.begin(), ary.end() - 1, ary.end() );
	}

	REP( i, 0, ary.size() )
	{
		if ( i )
		{
			cout << ' ';
		}
		cout << ary[i];
	}
	cout << endl;

	return 0;
}