제출 #594083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594083		Zanite	Genetics (BOI18_genetics)	C++17	0 / 100	323 ms	33500 KiB

genetics

// I am now here, but I have yet to prove that I am worthy of my place here.

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using ll	= long long;

const int maxN	= 4101;

const ll mod	= 1'690'758'499;
const ll maxW	= 420'000;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll getRand(ll l, ll r) {
	return uniform_int_distribution<ll>(l, r)(rng);
}

inline void maddto(ll &x, ll y) {x += y; if (x > mod) x -= mod;}

inline ll msub(ll x, ll y) {x -= y; if (x < 0) x += mod; return x;}
inline ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}

int N, M, K;
int DNA[4][maxN][maxN];
char corr[256];
char buf;

ll w[maxN], sumW;
ll columnSum[4][maxN];

#define debug(x) //cout << #x << " = " << x << '\n'

int main() {
	corr[(int)'A'] = 0;
	corr[(int)'C'] = 1;
	corr[(int)'G'] = 2;
	corr[(int)'T'] = 3;

	scanf("%d %d %d", &N, &M, &K);
	K = M - K;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf(" %c", &buf);
			DNA[corr[buf]][i][j] = 1;
		}

		w[i] = getRand(1, maxW);
		maddto(sumW, w[i]);

		debug(w[i]);
	}
	debug(sumW);

	for (int j = 1; j <= M; j++) {
		for (int d = 0; d < 4; d++) {
			for (int i = 1; i <= N; i++) {
				maddto(columnSum[d][j], w[i] * DNA[d][i][j]);
			}
			debug(d); debug(j); debug(columnSum[d][j]);
		}
	}

	for (int comp = 1; comp <= N; comp++) {
		ll target = mmul(K, msub(sumW, w[comp]));
		ll total = 0;
		for (int d = 0; d < 4; d++) {
			for (int col = 1; col <= N; col++) {
				maddto(total, mmul(DNA[d][comp][col], msub(columnSum[d][col], mmul(w[comp], DNA[d][comp][col]))));
			}
		}

		if (target == total) {
			printf("%d\n", comp);
			return 0;
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

genetics.cpp: In function 'int main()':
genetics.cpp:49:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |    DNA[corr[buf]][i][j] = 1;
      |             ^~~
genetics.cpp:49:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |    DNA[corr[buf]][i][j] = 1;
      |        ~~~~~~~~^
genetics.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d %d %d", &N, &M, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:48:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |    scanf(" %c", &buf);
      |    ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26