Submission #129189

#	Time	Username	Problem	Language	Result	Execution time	Memory
129189		mahmoudbadawy	Lamps (JOI19_lamps)	C++17	100 / 100	719 ms	145544 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int mem[N][16];
int cost[16][16];
int eff[16][2];
int n;
string a,b;

vector< vector<int> > conv = {{}, {0}, {1}, {2}, {0,1} , {1,0}, {0,2}, {2,0}, {1,2}, {2,1} , {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}};

int get(int mas,int b)
{
	vector<int> v=conv[mas];
	for(int i:v)
	{
		if(i==0) b=0;
		else if(i==1) b=1;
		else b=1-b;
	}
	return b;
}

int calc(int a,int b)
{
	vector<int> x=conv[a],y=conv[b];
	/*int j=0;
	for(int i=0;i<x.size()&&j<y.size();i++)
	{
		if(x[i]==y[j]) j++;
	}*/
	int maxi=0;;
	for(int i=0;i<(1<<x.size());i++)
	{
		for(int j=0;j<(1<<y.size());j++)
		{
			vector<int> p1,p2;
			for(int k=0;k<max(x.size(),y.size());k++)
			{
				if(i&(1<<k)) p1.push_back(k);
				if(j&(1<<k)) p2.push_back(k);
			}
			int cur=0;
			for(int k=0;k<min(p1.size(),p2.size());k++)
				if(x[p1[k]]==y[p2[k]]) cur++;
			maxi=max(maxi,cur);
		}
	}
	return y.size()-maxi;
}

int go(int ind,int mas)
{
	//cout << ind << " " << mas << endl;
	if(ind>=n) return 0;
	if(mem[ind][mas]!=-1) return mem[ind][mas];
	mem[ind][mas]=(1<<30);
	for(int i=0;i<16;i++)
	{
		if(eff[i][a[ind]-'0']==b[ind]-'0')
		{
			mem[ind][mas]=min(mem[ind][mas],cost[mas][i]+go(ind+1,i));
		}
	}
	return mem[ind][mas];
}

int main()
{
	cin >> n >> a >> b;
	memset(mem,-1,sizeof mem);
	for(int i=0;i<16;i++)
	{
		for(int j=0;j<16;j++)
		{
			cost[i][j]=calc(i,j);
		}
	}
	//cout << "OK" << endl;
	for(int i=0;i<16;i++)
	{
		for(int k=0;k<2;k++)
			eff[i][k]=get(i,k);
	}
	//cout << "OK" << endl;
	cout << go(0,0) << endl;
}

Compilation message (stderr)

lamp.cpp: In function 'int calc(int, int)':
lamp.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<max(x.size(),y.size());k++)
                ~^~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<min(p1.size(),p2.size());k++)
                ~^~~~~~~~~~~~~~~~~~~~~~~~~

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