torus711 のアレ

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

AOJ 0514 : Quality Checking

解法

2-pass で求めることができます。
まず一回目、成功した回について、そのときに使われた部品は正常であることが分かります。
次に二回目、失敗した回について、正常な部品が二つ使われていれば、残りのパーツは故障しています。
この二度の走査で求まらなかった部品は不明となります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

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

VI solve( int a, int b, int c )
{
	const int N = a + b + c;
	VI parts( N, 2 );

	int m;
	cin >> m;

	VVI nums( m, VI( 3 ) );
	VI rs( m );

	REP( i, 0, m )
	{
		REP( j, 0, 3 )
		{
			cin >> nums[i][j];
			nums[i][j]--;
		}
		cin >> rs[i];

		if ( !rs[i] )
		{
			continue;
		}

		REP( j, 0, 3 )
		{ 
			parts[ nums[i][j] ] = 1;
		}
	}

	REP( i, 0, m )
	{
		if ( rs[i] )
		{
			continue;
		}

		int count = 0;
		REP( j, 0, 3 )
		{
			count += parts[ nums[i][j] ] == 1;
		}

		if ( count != 2 )
		{
			continue;
		}

		REP( j, 0, 3 )
		{
			if ( parts[ nums[i][j] ] == 1 )
			{
				continue;
			}
			parts[ nums[i][j] ] = 0;
		}
	}

	return parts;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );
	
	while ( true )
	{
		int a, b, c;
		cin >> a >> b >> c;

		if ( !( a | b | c ) )
		{
			break;
		}

		VI res( solve( a, b, c ) );
		FOR( r, res )
		{
			cout << r << endl;
		}
	}

	return 0;
}