Submission #625419

# Submission time Handle Problem Language Result Execution time Memory
625419 2022-08-10T11:37:57 Z Augustyn JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
8 ms 3036 KB
#include <bits/stdc++.h>
using namespace std;
int n,k,odp=INT_MAX,ile[3],gdzie[3],pref[200001][3];
char ciag[200001];
int main()
{
	scanf("%d%d",&n,&k);
	char wcz=getchar();
	while(wcz!='J'&&wcz!='O'&&wcz!='I')
		wcz=getchar();
	for(int i=1;i<=n;++i)
	{
		ciag[i]=wcz;
		for(int j=0;j<3;++j)
			pref[i][j]=pref[i-1][j];
		if(ciag[i]=='J')
			++pref[i][0];
		else if(ciag[i]=='O')
			++pref[i][1];
		else
			++pref[i][2];
		wcz=getchar();
	}
	while(ile[0]<k)
	{
		++gdzie[0];
		if(gdzie[0]>n)
		{
			printf("-1");
			return 0;
		}
		if(ciag[gdzie[0]]=='J')
			++ile[0];
	}
	gdzie[1]=gdzie[0];
	while(ile[1]<k)
	{
		++gdzie[1];
		if(gdzie[1]>n)
		{
			printf("-1");
			return 0;
		}
		if(ciag[gdzie[1]]=='O')
			++ile[1];
	}
	gdzie[2]=gdzie[1];
	while(ile[2]<k)
	{
		++gdzie[2];
		if(gdzie[2]>n)
		{
			printf("-1");
			return 0;
		}
		if(ciag[gdzie[2]]=='I')
			++ile[2];
	}
	odp=gdzie[2]-3*k;
	for(int i=2;i<=n;++i)
	{
		if(ciag[i-1]=='J')
		{
			int gpam=gdzie[0];
			--ile[0];
			while(ile[0]<k)
			{
				++gdzie[0];
				if(gdzie[0]>n)
				{
					printf("%d",odp);
					return 0;
				}
				if(ciag[gdzie[0]]=='J')
					++ile[0];
			}
			if(gdzie[0]>gdzie[1])
			{
				gdzie[1]=gdzie[0];
				ile[1]=0;
			}
			else
			{
				ile[1]-=pref[gdzie[0]][1]-pref[gpam][1];
			}


			gpam=gdzie[1];
			while(ile[1]<k)
			{
				++gdzie[1];
				if(gdzie[1]>n)
				{
					printf("%d",odp);
					return 0;
				}
				if(ciag[gdzie[1]]=='O')
					++ile[1];
			}
			if(gdzie[1]>gdzie[2])
			{
				gdzie[2]=gdzie[1];
				ile[2]=0;
			}
			else
			{
				ile[2]-=pref[gdzie[1]][2]-pref[gpam][2];
			}

			while(ile[2]<k)
			{
				++gdzie[2];
				if(gdzie[2]>n)
				{
					printf("%d",odp);
					return 0;
				}
				if(ciag[gdzie[2]]=='I')
					++ile[2];
			}
		}
		odp=min(odp,gdzie[2]-i+1-3*k);
	}
	printf("%d",odp);
	return 0;
}

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 308 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 1 ms 312 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 308 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 1 ms 312 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 6 ms 2772 KB Output is correct
37 Correct 6 ms 3036 KB Output is correct
38 Correct 6 ms 3004 KB Output is correct
39 Correct 8 ms 3028 KB Output is correct
40 Correct 5 ms 3028 KB Output is correct
41 Correct 7 ms 3028 KB Output is correct
42 Correct 8 ms 3028 KB Output is correct
43 Correct 3 ms 2004 KB Output is correct
44 Correct 4 ms 2364 KB Output is correct
45 Correct 4 ms 3004 KB Output is correct
46 Correct 4 ms 3028 KB Output is correct
47 Correct 5 ms 3008 KB Output is correct
48 Correct 4 ms 3028 KB Output is correct
49 Correct 4 ms 2132 KB Output is correct
50 Correct 5 ms 3012 KB Output is correct
51 Correct 4 ms 3028 KB Output is correct
52 Correct 4 ms 2876 KB Output is correct
53 Correct 5 ms 3008 KB Output is correct
54 Correct 3 ms 3028 KB Output is correct
55 Correct 4 ms 3008 KB Output is correct
56 Correct 3 ms 3028 KB Output is correct