Submission #949528

#	Time	Username	Problem	Language	Result	Execution time	Memory
949528		pcc	Lamps (JOI19_lamps)	C++17	4 / 100	7 ms	4612 KiB

lamp

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


int N;
string s;
ll ans = 1e9;

int dist[1<<20];
queue<int> q;

void S1(){
	memset(dist,-1,sizeof(dist));
	cin>>s;
	int a = 0,b = 0;
	for(int i = 0;i<N;i++){
		if(s[i] == '1')a |= 1<<i;
	}
	cin>>s;
	for(int i = 0;i<N;i++){
		if(s[i] == '1')b |= 1<<i;
	}
	dist[a] = 0;
	q.push(a);
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		for(int l = 0;l<N;l++){
			int ta = now,tb = now,tc = now;
			for(int r = l;r<N;r++){
				ta |= 1<<r;
				if(tb&(1<<r))tb ^= (1<<r);
				tc ^= 1<<r;
				if(dist[ta] == -1){
					dist[ta] = dist[now]+1;
					q.push(ta);
				}
				if(dist[tb] == -1){
					dist[tb] = dist[now]+1;
					q.push(tb);
				}
				if(dist[tc] == -1){
					dist[tc] = dist[now]+1;
					q.push(tc);
				}
			}
		}
	}
	cout<<dist[b];
}

void S3(){
	string a,b;
	cin>>a>>b;
	char pre = '0';
	int ans = 0;
	for(auto &i:b){
		if(i == '1'&&pre == '0')ans++;
		pre = i;
	}
	cout<<ans;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	if(N<=8)S1();
	else S3();
}

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