Submission #51317

#	Time	Username	Problem	Language	Result	Execution time	Memory
51317		ho94949	Rope (JOI17_rope)	C++17	55 / 100	2552 ms	13580 KiB

rope

#include<bits/stdc++.h>
using namespace std;
int N, K;
int arr[1010101];
int ans[1010101];
int cnt[1010101];
int evalodd(int c)
{
	memset(cnt+1, 0, sizeof(int)*K);
	int ans = 0;
	if(arr[0] != c) cnt[arr[0]]++;
	else ++ans;
	for(int i=0; i<(N-1)/2; ++i)
	{
		int l = arr[2*i+1], r = arr[2*i+2];
		if(l == c && r == c)
			ans += 2;
		else if(l == c || r == c)
			ans++;
		else
			cnt[l]++, cnt[r]++;
	}
	if(N%2==0)
	{
		if(arr[N-1] != c)
			cnt[arr[N-1]]++;
		else
			++ans;
	}
	/*
	puts("==O==");
	printf("%d\n", c);
	for(int i=1; i<=K; ++i)
		printf("%d ", cnt[i]);
	printf("\n%d\n", ans);
	puts("=====");
	*/
	return ans + *max_element(cnt+1, cnt+K+1);
}
int evaleven(int c)
{
	memset(cnt+1, 0, sizeof(int)*K);
	int ans = 0;
	for(int i=0; i<N/2; ++i)
	{
		int l = arr[2*i], r = arr[2*i+1];
		if(l == c && r == c)
			ans += 2;
		else if(l == c || r == c)
			ans++;
		else
			cnt[l]++, cnt[r]++;
	}
	if(N%2==1)
	{
		if(arr[N-1] != c)
			cnt[arr[N-1]]++;
		else
			++ans;
	}
	/*
	puts("==E==");
	printf("%d\n", c);
	for(int i=1; i<=K; ++i)
		printf("%d ", cnt[i]);
	printf("\n%d\n", ans);
	puts("=====");
	*/
	return ans + *max_element(cnt+1, cnt+K+1);
}
int main()
{
	scanf("%d%d", &N, &K);
	for(int i=0; i<N; ++i) scanf("%d", arr+i);
	for(int i=1; i<=K; ++i)
		ans[i] = 0x3f3f3f3f;
	for(int i=1; i<=K; ++i)
		printf("%d\n", N-max(evaleven(i), evalodd(i)));
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
rope.cpp:74:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; ++i) scanf("%d", arr+i);
                         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20