概要
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; }