Yuki No.387 ハンコ ( Bitset )

No.387 ハンコ - yukicoder
bitsetで塗る部分を処理するだけで32倍早くなるあれ。
動的宣言できないんだなbitset。

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

typedef vector< int > vi;
typedef vector< vi > vvi;

const int MAXN = 1e5 + 5;
const int MAXCOL = 1e5;

int main(){
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );

    int N; cin >> N;

    vi A( N ), B( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    for( int i = 0; i < N; ++i )
        cin >> B[ i ];

    vvi C( MAXCOL ); // positions of a particular color
    for( int i = 0; i < N; ++i )
        C[ A[ i ] ].push_back( i );

    bitset< 2 * MAXN - 1 > stamp;
    for( int i = 0; i < N; ++i )
        stamp[ i ] = B[ i ];

    bitset< 2 * MAXN - 1 > paper;
    for( int i = 1; i <= MAXCOL; ++i ){
        bitset< 2 * MAXN - 1 > ink;
        for( int p : C[ i ] )
            ink |= stamp << p;
        paper ^= ink;
    }

    for( int i = 0; i < 2 * N - 1; ++i )
        cout << ( paper[ i ] ? "ODD" : "EVEN" ) << "\n";

    return 0;
}