oj.uz

Submission #129151

# Submission time Handle Problem Language Result Execution time Memory
129151 2019-07-11T18:17:26 Z mahmoudbadawy Lamps (JOI19_lamps) C++17
0 / 100
 1000 ms 14432 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int d1[N],d2[N];
int bl[2][N];
int mem[N];
string a,b;
int n;

int stat(int x)
{
	if(x<0) return stat(0);
	// 0 01 1 10 2 00 3 11
	if(a[x]==b[x])
		return (a[x]=='0'?2:3);
	return (a[x]=='0'?0:1);
}

int f1(int x,int y)
{
	return d1[y]-(x?d1[x-1]:0)+(stat(x)<2 && stat(x)==stat(x-1));
}

int f2(int x,int y)
{
	return d2[y]-(x?d2[x-1]:0)+(stat(x)>=2 && stat(x)==stat(x-1) );
}

int f3(int x,int y)
{
	return min(bl[1][y]-(x?bl[1][x-1]:0),bl[0][y]-(x?bl[0][x-1]:0));
}

vector<int> cmp;
int pos[N],st[N];

int main()
{
	cin >> n >> a >> b;
	cmp.push_back(stat(0));
	for(int i=1;i<n;i++)
	{
		if(stat(i)==cmp.back())
			pos[i]=pos[i-1];
		else
		{
			pos[i]=cmp.size();
			st[cmp.size()]=i;
			cmp.push_back(stat(i));
		}
	}
	for(int i=1;i<n;i++)
	{
		d1[i]=(stat(i)!=stat(i-1)&&(stat(i)<2))+d1[i-1];
		int mn=cmp[pos[i]],mx=cmp[pos[i]-1];
		d2[i]=((stat(i)!=stat(i-1))&&(stat(i)>=2))+d2[i-1];
		/*if(stat(i)!=stat(i-1))
		{
			if(pos[i]>=2&&cmp[pos[i]]==cmp[pos[i]-2] && a[i]!=a[i-1])
			{
				if(stat(i)<2)
					d1[i]--;
				if(stat(i)>=2)
					d2[i]--;
			}
		}*/
	}
	/*for(int i=0;i<n;i++)
		cout << d1[i] << " ";
	cout << endl;
	for(int i=0;i<n;i++)
		cout << d2[i] << " ";
	cout << endl;*/
	for(int i=n-1;i>=0;i--)
	{
		mem[i]=(1<<30);
		bl[b[i]-'0'][i]++;
		if(i+1<n&&b[i]!=b[i+1])
		{
			for(int j=i+1;j<n;j++)
				bl[b[i]-'0'][j]++;
		}
		if(pos[i]+2<cmp.size() && st[pos[i]+1]==i+1)
		{
			int ind=st[pos[i]+2];
			//cout << i << " " << ind << ": GOT :)" << endl;
			//cout << cmp[ind] << " " << cmp[i] << " " << a[ind] << " " << a[ind-1] << endl;
			if(stat(ind)==stat(i) && a[ind]!=a[ind-1])
			{
				for(int j=ind;j<n;j++)
				{
					if(stat(ind)<2)
						d1[j]--;
					if(stat(ind)>=2)
						d2[j]--;
				}
			}
		}
		for(int j=i;j<n;j++)
		{
			//cout << i << " " << j << " : " << f1(i,j) << " " << f2(i,j) << " " << f3(i,j)  << " " << mem[j+1] << endl;
			mem[i]=min(mem[i],min(f1(i,j),min(1+f2(i,j),1+f3(i,j)))+mem[j+1]);
		}
	}
	cout << mem[0] << endl;
}

Compilation message

lamp.cpp: In function 'int main()':
lamp.cpp:58:7: warning: unused variable 'mn' [-Wunused-variable]
   int mn=cmp[pos[i]],mx=cmp[pos[i]-1];
       ^~
lamp.cpp:58:22: warning: unused variable 'mx' [-Wunused-variable]
   int mn=cmp[pos[i]],mx=cmp[pos[i]-1];
                      ^~
lamp.cpp:86:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pos[i]+2<cmp.size() && st[pos[i]+1]==i+1)
      ~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Incorrect 2 ms 376 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Incorrect 2 ms 376 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Execution timed out 1062 ms 14432 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Incorrect 2 ms 376 KB Output isn't correct
27 Halted 0 ms 0 KB -