Submission #129170

#	Time	Username	Problem	Language	Result	Execution time	Memory
129170		mahmoudbadawy	Lamps (JOI19_lamps)	C++17	10 / 100	384 ms	4912 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

string a,b;
int n;
int dis[(1<<18)];

int conv(string s)
{
	int res=0;
	for(int i=0;i<s.size();i++)
		res=res*2+(s[i]-'0');
	return res;
}

int main()
{
	cin >> n >> a >> b;
	if(a==string(n,'0'))
	{
		int ans[2]={b[0]=='0',b[0]=='1'};
		for(int i=1;i<b.size();i++)
		{
			if(b[i]!=b[i-1])
				ans[b[i]-'0']++;
		}
		cout << min(ans[1],1+ans[0]) << endl;
		return 0;
	}
	queue<int> q;
	q.push(conv(a));
	int bb=conv(b);
	memset(dis,-1,sizeof dis);
	dis[conv(a)]=0;
	while(q.size())
	{
		int s=q.front(); q.pop();
		if(s==bb) break;
		for(int i=0;i<n;i++)
		{
			int sd=s;
			for(int j=i;j<n;j++)
			{
				sd&=(~(1<<j));
				if(dis[sd]!=-1) continue;
				dis[sd]=dis[s]+1;
				q.push(sd);
			}
		}
		for(int i=0;i<n;i++)
		{
			int sd=s;
			for(int j=i;j<n;j++)
			{
				sd|=(1<<j);
				if(dis[sd]!=-1) continue;
				dis[sd]=dis[s]+1;
				q.push(sd);
			}
		}
		for(int i=0;i<n;i++)
		{
			int sd=s;
			for(int j=i;j<n;j++)
			{
				sd^=(1<<j);
				if(dis[sd]!=-1) continue;
				dis[sd]=dis[s]+1;
				q.push(sd);
			}
		}
	}
	cout << dis[bb] << endl;
	
}

Compilation message (stderr)

lamp.cpp: In function 'int conv(std::__cxx11::string)':
lamp.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++)
              ~^~~~~~~~~
lamp.cpp: In function 'int main()':
lamp.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<b.size();i++)
               ~^~~~~~~~~

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