torus711 のアレ

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

Codeforces #155, Division 2, A : Cards with Numbers

概要

2N 枚のカードがあり、それぞれには一つの整数が書かれている。
このカードを使ってゲームをするので、このカードを使ってゲームをするので、N 枚ずつに分けたい。
全く同じ二つの集合に分けられるならばその分け方を、できないならば -1 を出力せよ。

解法

各数字について、そのインデックスを覚えます。
インデックスの数が奇数となる数が存在すれば、分けることはできないので -1 です。
それ以外のとき、各数字についてインデックスを二つずつ適当に出力するだけで解けます。

コード

typedef vector<int> VI;

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

#define ITER( c ) __typeof( (c).begin() )
#define IREP( c, it ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )

#define PB( n ) push_back( n )

#define fst first
#define snd second

bool check( map< int, VI > mapping )
{
	IREP( mapping, it )
	{
		if ( (*it).snd.size() % 2 )
		{
			return false;
		}
	}

	return true;
}

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

#ifdef ONLINE_JUDGE
	freopen( "input.txt", "r", stdin );
	freopen( "output.txt", "w", stdout );
#endif

	int n;
	cin >> n;

	map< int, VI > mapping;

	REP( i, 0, n * 2 )
	{
		int a;
		cin >> a;

		mapping[a].PB( i + 1 );
	}

	if ( check( mapping ) )
	{
		IREP( mapping, it )
		{
			REP( i, 0, (*it).snd.size() )
			{
				cout << (*it).snd[i] << ( i % 2 ? '\n' : ' ' );
			}
		}
	}
	else
	{
		cout << -1 << endl;
	}

	return 0;
}