제출 #825430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825430		QwertyPi	Genetics (BOI18_genetics)	C++14	100 / 100	923 ms	33412 KiB

genetics

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

const int MAXN = 4100 + 11;
const int MOD = 1e9 + 7;
bitset<4100> A0[4100], A1[4100];
bitset<4100> B, B0, B1;
int f(char c){
	if(c == 'A') return 0;
	if(c == 'C') return 1;
	if(c == 'G') return 2;
	if(c == 'T') return 3;
}

bool fail[MAXN];
int a[MAXN];
int b[MAXN][4];
char _c[MAXN][MAXN];
int32_t main(){
	random_device rd;
	mt19937 rng(rd());

	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < n; i++) a[i] = rng();
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			char c; cin >> c; _c[i][j] = c;
			b[j][f(c)] += a[i];
		}
	}

	for(int j = 0; j < m; j++){
		for(int k = 0; k < 4; k++){
			b[j][k] %= MOD;
		}
	}

	for(int i = 0; i < n; i++){
		int s = 0, rs = 0;
		for(int j = 0; j < n; j++){
			if(i != j) s += k * a[j];
		}
		s %= MOD;
		for(int j = 0; j < m; j++){
			for(int k = 0; k < 4; k++){
				if(k != f(_c[i][j])) rs += b[j][k];
			}
		}
		rs %= MOD;
		if(s == rs){
			cout << i + 1 << endl;
			return 0;
		}
	}
}

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

genetics.cpp: In function 'long long int f(char)':
genetics.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

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