QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358876 | #7940. Impossible Numbers | UNos_maricones | WA | 0ms | 3472kb | C++20 | 1.7kb | 2024-03-20 06:33:06 | 2024-03-20 06:33:07 |
Judging History
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'