Submission #20926

#	Time	Username	Problem	Language	Result	Execution time	Memory
20926		gs14004	Rope (JOI17_rope)	C++11	45 / 100	29 ms	5924 KiB

rope

#include <bits/stdc++.h>
typedef long long lint;
typedef long double llf;
using namespace std;
typedef pair<int, int> pi;

int n, m, a[1000005];
int ans[11];

int solve(int s, int e, int x, int y){
	int ans = 0;
	for(int i=s+1; i<=e; i+=2){
		ans += min((a[i-1] != x) + (a[i] != x), (a[i-1] != y) + (a[i] != y));
	}
	return ans;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
	}
	if(m > 10) return 0;
	memset(ans, 0x3f, sizeof(ans));
	if(n % 2 == 0){
		for(int i=1; i<=m; i++){
			for(int j=1; j<=i; j++){
				int x = solve(1, n, i, j);
				int y = solve(2, n-1, i, j) + (a[1] != i && a[1] != j) + (a[n] != i && a[n] != j);
				ans[i] = min({ans[i], x, y});
				ans[j] = min({ans[j], x, y});
			}
		}
	}
	else{
		for(int i=1; i<=m; i++){
			for(int j=1; j<=i; j++){
				int x = solve(1, n-1, i, j) + (a[n] != i && a[n] != j);
				int y = solve(2, n, i, j) + (a[1] != i && a[1] != j);
				ans[i] = min({ans[i], x, y});
				ans[j] = min({ans[j], x, y});
			}
		}
	}
	for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:19:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
rope.cpp:21:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

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