제출 #129180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129180		mahmoudbadawy	Lamps (JOI19_lamps)	C++17	10 / 100	691 ms	143588 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++;
	}
	return y.size()-j;
}

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;
}

컴파일 시 표준 에러 (stderr) 메시지

lamp.cpp: In function 'int calc(int, int)':
lamp.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<x.size()&&j<y.size();i++)
              ~^~~~~~~~~
lamp.cpp:31:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<x.size()&&j<y.size();i++)
                          ~^~~~~~~~~

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