Submission #51310

#	Time	Username	Problem	Language	Result	Execution time	Memory
51310		ho94949	Rope (JOI17_rope)	C++17	45 / 100	2567 ms	3216 KiB

rope

#include<bits/stdc++.h>
using namespace std;
int N, K;
int arr[1010101];
int ans[1010101];
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)
		for(int j=1; j<=K; ++j)
		{
			int v1 = 0, v2 = 0;
			for(int k=0; k<N/2; ++k)
			{
				int l = arr[2*k], r = arr[2*k+1];
				if(l==r && (l==i || l==j)) v1 += 2;
				else if(l==i || l==j || r==i || r==j) ++v1;
			}
			if(N%2==1 && (arr[N-1] == i || arr[N-1] == j)) ++v1;
			
			if(arr[0] == i || arr[0] == j) ++ v2;
			for(int k=0; k<(N-1)/2; ++k)
			{
				int l = arr[2*k+1], r = arr[2*k+2];
				if(l==r && (l==i || l==j)) v2 += 2;
				else if(l==i || l==j || r==i || r==j) ++v2;
			}
			if(N%2==0 && (arr[N-1] == i || arr[N-1] == j)) ++v2;
			
			//printf("%d %d %d %d\n", i, j, v1, v2);
			ans[i] = min(ans[i], N-max(v1, v2));
			ans[j] = min(ans[j], N-max(v1, v2));
		}
	for(int i=1; i<=K; ++i)
		printf("%d\n", ans[i]);
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:8: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:9: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: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20