oj.uz

Submission #129183

# Submission time Handle Problem Language Result Execution time Memory
129183 2019-07-11T19:33:29 Z mahmoudbadawy Lamps (JOI19_lamps) C++17
0 / 100
 657 ms 143516 KB 
#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 j=0;
	for(int i=0;i<y.size();i++)
	{
		for(int k=0;k<x.size();k++)
			j+=(y[i]==x[k]);
	}
	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;
}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 54 ms 62968 KB Output is correct
3 Correct 53 ms 62968 KB Output is correct
4 Correct 53 ms 62968 KB Output is correct
5 Correct 53 ms 62968 KB Output is correct
6 Correct 54 ms 62968 KB Output is correct
7 Correct 53 ms 62968 KB Output is correct
8 Incorrect 54 ms 62972 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 54 ms 62968 KB Output is correct
3 Correct 53 ms 62968 KB Output is correct
4 Correct 53 ms 62968 KB Output is correct
5 Correct 53 ms 62968 KB Output is correct
6 Correct 54 ms 62968 KB Output is correct
7 Correct 53 ms 62968 KB Output is correct
8 Incorrect 54 ms 62972 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62952 KB Output is correct
2 Correct 53 ms 62968 KB Output is correct
3 Correct 53 ms 62944 KB Output is correct
4 Correct 53 ms 62968 KB Output is correct
5 Correct 54 ms 62968 KB Output is correct
6 Correct 54 ms 62968 KB Output is correct
7 Correct 647 ms 143344 KB Output is correct
8 Incorrect 657 ms 143516 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 54 ms 62968 KB Output is correct
3 Correct 53 ms 62968 KB Output is correct
4 Correct 53 ms 62968 KB Output is correct
5 Correct 53 ms 62968 KB Output is correct
6 Correct 54 ms 62968 KB Output is correct
7 Correct 53 ms 62968 KB Output is correct
8 Incorrect 54 ms 62972 KB Output isn't correct
9 Halted 0 ms 0 KB -