StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I suggest the following algorithm: <br/> 1. Initially consider all <code>C[ i ]</code> as empty nests.<br/> 2. For each i where <code>B[ i ] = 0</code> we put <code>C[ i ] = A[ i ]</code><br/> 3. Go through array <strong>from left to right</strong>, and for each <code>i</code> where <code>B[ i ] = -1</code> put <br/> <code>C[ j ] = A[ i ]</code>, where <code>0 <= j < i</code> is the <strong>smallest</strong> index for which <code>C[ j ]</code> is still empty. If no such index exists, the answer is impossible.<br/> 4. Go through array <strong>from right to left</strong>, and for each <code>i</code> where <code>B[ i ] = 1</code> put <br/> <code>C[ j ] = A[ i ]</code>, where <code>i < j < n</code> is the <strong>greatest</strong> index for which <code>C[ j ]</code> is still empty. If no such index exists, the answer is impossible.<br/></p> <p>Why do we put A[ i ] to the leftmost position in step 2 ? Well, we know that we <strong>must</strong> put it to some position j < i. On the other hand, putting it leftmost will increase our changes to not get stucked in step 3. See this example for illustration: <br/></p> <pre><code>A: [ 1, 2, 3 ] B: [ 1, 1,-1 ] </code></pre> <p>Initially C is empty: <code>C:[ _, _, _ ]</code><br/> We have no 0-s, so let's pass to step 2.<br/> We have to choose whether to place element <code>A[ 2 ]</code> to <code>C[ 0 ]</code> or to <code>C[ 1 ]</code>.<br/> If we place it <strong>not</strong> leftmost, we will get the following situation:<br/> <code>C: [ _, 3, _ ]</code> <br/> And... Oops, we are unable to arrange elements <code>A[ 0 ]</code> and <code>A[ 1 ]</code> due to insufficient place :( <br/> <strong>But</strong>, if we put A[ 2 ] leftmost, we will get <br/> <code>C: [ 3, _, _ ]</code>, And it is pretty possible to finish the algorithm with<br/> <code>C: [ 3, 1, 2 ]</code> :)<br/><br/> <strong>Complexity</strong>: <br/> What we do is pass three times along the array, so the complexity is <code>O(3n) = O(n)</code> - linear. <br/> <br/> <strong>Further example:</strong><br/></p> <pre><code>A: [ 1, 2, 3 ] B: [ 1, -1, -1 ] </code></pre> <p>Let's go through the algorithm step by step:<br/> 1. <code>C: [ _, _, _ ]</code><br/> 2. Empty, because no 0-s in <code>B</code><br/> 3. Putting <code>A[ 1 ]</code> and <code>A[ 2 ]</code> to leftmost empty positions:<br/></p> <pre><code>C: [ 2, 3, _ ] </code></pre> <p>4. Putting <code>A[ 0 ]</code> to the rightmost free (in this example the only one) free position:<br/></p> <pre><code>C: [ 2, 3, 1 ] </code></pre> <p>Which is the answer.<br/> <br/> <strong>Source code:</strong></p> <pre><code>#include <iostream> #include <string> #include <vector> using namespace std; vector< int > a; vector< int > b; vector< int > c; int n; bool solve () { int i; for( i = 0; i < n; ++i ) c[ i ] = -1; for( i = 0; i < n; ++i ) if( b[ i ] == 0 ) c[ i ] = a[ i ]; int leftmost = 0; for( i = 0; i < n; ++i ) if( b[ i ] == -1 ) { for( ; leftmost < i && c[ leftmost ] != -1; ++leftmost ); // finding the leftmost free cell if( leftmost >= i ) return false; // not found c[ leftmost++ ] = a[ i ]; } int rightmost = n - 1; for( i = n - 1; i >= 0; --i ) if( b[ i ] == 1 ) { for( ; rightmost > i && c[ rightmost ] != -1; --rightmost ); // finding the rightmost free cell if( rightmost <= i ) return false; // not found; c[ rightmost-- ] = a[ i ]; } return true; } int main () { cin >> n; a.resize(n); b.resize(n); c.resize(n); int i; for( i = 0; i < n; ++i ) cin >> a[ i ]; for( i = 0; i < n; ++i ) cin >> b[ i ]; if( !solve() ) cout << "Impossible"; else for( i = 0; i < n; ++i ) cout << c[ i ] << ' '; cout << endl; return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload