QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358876#7940. Impossible NumbersUNos_mariconesWA 0ms3472kbC++201.7kb2024-03-20 06:33:062024-03-20 06:33:07

Judging History

你现在查看的是最新测评结果

  • [2024-03-20 06:33:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3472kb
  • [2024-03-20 06:33:06]
  • 提交

answer

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

const int M = 6;
const int D = 10;
const int INF = (int) 1e9;

int main() {
	cin.tie( NULL );
	ios_base::sync_with_stdio( 0 );

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

	vector< int > mask( n );
	for( int i = 0; i < n; ++ i )
	{
		for( int j = 0; j < M; ++ j )
		{
			int x;
			cin >> x;
			mask[i] |= ( 1 << x );
		}
	}

	for( int d = 1; ; ++ d )
	{
		vector< pair< int, int > > rem;
		for( int mk = 0; mk < ( 1 << D ); ++ mk )
		{
			int cn = 0;
			for( int i = 0; i < n; ++ i )
				if( mask[i] & mk ) 
					++cn;
                        if( cn < d - 1 )
			  rem.push_back( { mk, cn } );
		}

		string curr = "";
		function< void( int, bool, vector< pair< int, int > >  ) > solve = [&]( int rd, bool all, vector< pair< int, int > > rem ) {
			if( !all && rem.empty() ) return;

			if( rd == 0 )
			{
				if( all )
				{
					cout << curr;
					--k;
					if( k == 0 )
					{
						cout << '\n';
						exit( 0 );
					}
					cout << ' ';
				}
				return;
			}	

			for( int di = ( rd == d ); di < D; ++di )
			{
				bool n_all = all;	
				vector< pair< int, int > > n_rem;
				if( all == false )
				{
					int mn = INF;
					for( auto [mk,cn]: rem )
					{
						const int n_cn = cn - ( mk >> di & 1);
						if( n_cn < rd - 1 )
						{
							n_rem.push_back( { mk, n_cn });
							mn = min( mn, n_cn );
						}
					}

					if( mn < 0 ) 
					{
						n_all = true;
						n_rem.clear();
					}
				}

				curr.push_back( '0' + di );
				solve( rd - 1, n_all, n_rem );
				curr.pop_back();
			}
		};

		solve( d, false, rem );
	}


	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3472kb

input:

2 3
1 8 7 0 6 2
1 2 5 4 9 3

output:

100 106 107

result:

wrong answer 1st lines differ - expected: '33 34 35', found: '100 106 107'