Submission #543229

#	Time	Username	Problem	Language	Result	Execution time	Memory
543229		chonka	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	57 ms	492 KiB

chameleon

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

namespace {
    vector < int > v[ 1007 ] ;
    int col[ 1007 ] ;

    vector < int > w[ 3 ] ;
    vector < int > aux ;
    bool done[ 1007 ] ;
    int nxt[ 1007 ] , prv[ 1007 ] ;
}

void dfs ( int vertex , int c ) {
    col[ vertex ] = c ;
    for ( auto y : v[ vertex ] ) {
        if ( col[ y ] == 0 ) {
            dfs ( y , 3 - c ) ;
        }
    }
}

bool f ( int wh , int l , int r , int ori ) {
    if ( l > r ) { return false ; }
    aux.clear ( ) ;
    aux.emplace_back ( ori ) ;
    for ( int i = l ; i <= r ; ++ i ) {
        aux.emplace_back ( w[ wh ][ i ] ) ;
    }
    int ret = Query ( aux ) ;
    if ( ret <= r - l + 1 ) { return true ; }
    return false ;
}

void Solve ( int n ) {
    for ( int i = 1 ; i <= 2 * n ; ++ i ) {
        for ( int j = 1 ; j < i ; ++ j ) {
            col[ j ] = 0 ;
        }
        for ( int j = 1 ; j < i ; ++ j ) {
            if ( col[ j ] == 0 ) {
                dfs ( j , 1 ) ;
            }
        }
        w[ 1 ].clear ( ) ; w[ 2 ].clear ( ) ;
        for ( int j = 1 ; j < i ; ++ j ) {
            w[ col[ j ] ].push_back ( j ) ;
        }
        for ( int wh = 1 ; wh <= 2 ; ++ wh ) {
            int lst = -1 ;
            for ( int tm = 0 ; tm < 3 ; ++ tm ) {
                int l , r , mid ;
                l = lst + 1 ;
                r = w[ wh ].size ( ) - 1 ;
                if ( f ( wh , lst + 1 , r , i ) == false ) { break ; }
                while ( r - l > 3 ) {
                    mid = ( l + r ) / 2 ;
                    if ( f ( wh , lst + 1 , mid , i ) == true ) { r = mid ; }
                    else { l = mid ; }
                }
                while ( f ( wh , lst + 1 , l , i ) == false ) { ++ l ; }
                v[ i ].push_back ( w[ wh ][ l ] ) ;
                v[ w[ wh ][ l ] ].push_back ( i ) ;
                lst = l ;
            }
        }
    }
    for ( int i = 1 ; i <= 2 * n ; ++ i ) {
        if ( v[ i ].size ( ) == 1 && done[ i ] == false ) {
            Answer ( i , v[ i ][ 0 ] ) ;
            done[ i ] = done[ v[ i ][ 0 ] ] = true ;
        }
    }
    for ( int i = 1 ; i <= 2 * n ; ++ i ) {
        if ( v[ i ].size ( ) == 3 ) {
            for ( int j = 0 ; j < 3 ; ++ j ) {
                aux.clear ( ) ;
                aux.push_back ( i ) ;
                for ( int t = 0 ; t < 3 ; ++ t ) {
                    if ( j == t ) { continue ; }
                    aux.push_back ( v[ i ][ t ] ) ;
                }
                if ( Query ( aux ) == 1 ) {
                    nxt[ i ] = v[ i ][ j ] ;
                    prv[ v[ i ][ j ] ] = i ;
                    break ;
                }
            }
        }
    }
    for ( int i = 1 ; i <= 2 * n ; ++ i ) {
        if ( v[ i ].size ( ) == 3 && done[ i ] == false ) {
            int sm = v[ i ][ 0 ] + v[ i ][ 1 ] + v[ i ][ 2 ] ;
            sm = sm - prv[ i ] - nxt[ i ] ;
            Answer ( i , sm ) ;
            done[ i ] = done[ sm ] = true ;
        }
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36