結果

問題 No.1838 Modulo Straight
コンテスト
ユーザー 👑 ygussany
提出日時 2022-01-16 15:40:15
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 1,050 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 23,680 KB
最終ジャッジ日時 2024-11-23 11:05:01
合計ジャッジ時間 6,774 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

void add_BIT(int N, int BIT[], int i, int k)
{
	while (i <= N) {
		BIT[i] += k;
		i += (i & -i);
	}
}

int sum_BIT(int BIT[], int r)
{
	int sum = 0;
	while (r > 0) {
		sum += BIT[r];
		r -= (r & -r);
	}
	return sum;
}

void chmin(long long* a, long long b)
{
	if (*a > b) *a = b;
}

int main()
{
	int i, M, K, N, A[400001], num[400001] = {}, *p[400001];
	scanf("%d %d", &M, &K);
	for (i = 0; i < M; i++) p[i] = (int*)malloc(sizeof(int) * (K + 1));
	for (i = 1, N = M * K; i <= N; i++) {
		scanf("%d", &(A[i]));
		p[A[i]][++num[A[i]]] = i;
		A[i] += M * (num[A[i]] - 1) + 1;
	}
	
	int j, BIT[400001] = {}, dif[400001];
	long long ans = 0, tmp;
	for (i = 1; i <= N; i++) {
		ans += i - sum_BIT(BIT, A[i]) - 1;
		dif[i] = (sum_BIT(BIT, ((A[i] - 1) / M + 1) * M) - sum_BIT(BIT, ((A[i] - 1) / M) * M)) * 2 - (M - 1);
		add_BIT(N, BIT, A[i], 1);
	}
	for (i = M - 1, tmp = ans; i >= 1; i--) {
		for (j = 1; j <= K; j++) tmp += dif[p[i][j]];
		chmin(&ans, tmp);
	}
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}
0