Submission #293285

#	Time	Username	Problem	Language	Result	Execution time	Memory
293285		CaroLinda	Monochrome Points (JOI20_monochrome)	C++14	25 / 100	32 ms	504 KiB

monochrome

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mk make_pair
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define sz(x) (int)(x.size())

const int MAXN = 4010 ;

using namespace std ;

int N , ans ;
int myPair[MAXN] , qtd[MAXN][2] ;
vector<int> aux ;
vector<pii> lines ;
char str[MAXN] ;

int checkIntersection( pii p1 , pii p2 )
{

    int type1 = ( p2.ff > p1.ff && p2.ff < p1.ss )&( p2.ss > p1.ff && p2.ss < p1.ss ) ;
    int type2 = ( p2.ff > p1.ss || p2.ff < p1.ff )&( p2.ss > p1.ss || p2.ss < p1.ff ) ;

    return type1 == 0 && type2 == 0 ;

}

void test(int i)
{
    if( str[i] == str[0] ) return ;

    lines.clear() ;

    int idx = i ;

    lines.pb( mk(0,i) ) ;
    for(int j : aux )
    {

        idx = (idx == 2*N - 1) ? 0 : idx+1 ;
        while( str[idx] == str[j] )
        {
            if(idx == 2*N - 1) idx = 0 ;
            else idx++ ;
        }

        if( idx < j ) lines.pb(mk(idx,j)) ;
        else lines.pb( mk(j,idx) ) ;

    }

    int temp = 0 ;

    for(int a = 0 ; a < sz(lines) ; a++ )
    {
        int qtdBlack = qtd[ lines[a].ss - 1 ][0] - qtd[ lines[a].ff ][0] ;
        int qtdWhite = qtd[ lines[a].ss - 1 ][1] - qtd[ lines[a].ff ][1] ;

        temp += min( qtdBlack, N - 1 - qtdWhite ) + min( qtdWhite, N - 1 - qtdBlack ) ;

    }

    ans = max(ans, temp>>1) ;
}

int main()
{
    srand(time(0)) ;

    scanf("%d", &N ) ;
    scanf("%s", str ) ;

    for(int i = 0 ; i < 2*N ; i++ )
    {
        qtd[i][ (str[i] == 'W' ) ]++ ;

        qtd[i+1][0] = qtd[i][0];
        qtd[i+1][1] = qtd[i][1] ;

        if(str[i] == str[0] && i != 0) aux.pb(i) ;
    }

    vector<int> vec ;
    lp(i,0,2*N)
        if(str[i] != str[0]) vec.pb( i ) ;

    random_shuffle(all(vec)) ;

    for(int i = 0 ; i < min(N , 1000) ; i++ )
        test( vec[i] ) ;

    printf("%d\n" , ans ) ;

}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |     scanf("%d", &N ) ;
      |     ~~~~~^~~~~~~~~~~
monochrome.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%s", str ) ;
      |     ~~~~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65