Submission #792440

#	Time	Username	Problem	Language	Result	Execution time	Memory
792440		vjudge1	Lamps (JOI19_lamps)	C++14	10 / 100	837 ms	4244 KiB

lamp

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = 1e6 ;
int n ;
bool flag ;
char a[N + 1], b[N + 2] ;
int dist[N + 1] ;
void bfs()
{
    int num = 0 ;
    deque<int> d ;
    for(int i = 0 ; i < n ; i++)
        if(a[i] == '1')
            num ^= (1 << i) ;
    d.push_back(num) ;
    dist[num] = 1 ;
    while(d.size())
    {
        int now = d[0] ;
        d.pop_front() ;
        for(int i = 0 ; i < n ; i++)
            for(int j = i ; j < n ; j++)
            {
                int num1 = now, num2 = now, num3 = now ;
                for(int q = i ; q <= j ; q++)
                {
                    num1 |= (1 << q) ;
                    if(now & (1 << q))num2 ^= (1 << q) ;
                    num3 ^= (1 << q) ;
                }
                if(!dist[num1])
                {
                    d.push_back(num1) ;
                    dist[num1] = dist[now] + 1 ;
                }
                if(!dist[num2])
                {
                    d.push_back(num2) ;
                    dist[num2] = dist[now] + 1 ;
                }
                if(!dist[num3])
                {
                    d.push_back(num3) ;
                    dist[num3] = dist[now] + 1 ;
                }
            }
    }
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> a[i] ;
        if(a[i] == '1')
            flag = 1 ;
    }
    for(int i = 0 ; i < n ; i++)
        cin >> b[i] ;
    if(!flag)
    {
        int ans = 0 ;
        b[n] = '0' ;
        for(int i = 0 ; i < n ; i++)
            if(b[i] == '1' && b[i + 1] == '0')
                ans++ ;
        cout << ans ;
        return 0 ;
    }
    if(n <= 18)
    {
        int num = 0 ;
        bfs() ;
        for(int i = 0 ; i < n ; i++)
            if(b[i] == '1')num ^= (1 << i) ;
        cout << dist[num] - 1 ;
        return 0 ;
    }
    return 0 ;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49