제출 #395173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395173		wenqi	Genetics (BOI18_genetics)	C++14	27 / 100	2088 ms	110020 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

int N, M, K;

using H = uint64_t;

#define P1 30881

const H P2 = (1ll << 45) - 1;

char dna[4169][4169];

H coef[4169];

struct W {
	unordered_set<int> side;
	H hash;

	void c() {
		hash = 0;
		for (int i : side) {
			hash = (hash + coef[i]) & P2;
		}
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> K;

	coef[0] = 1;
	for(int i = 1; i <= N; i++) {
		cin >> dna[i];
		coef[i] = (coef[i - 1] * P1) & P2;
	}

	vector<pair<W, W>> bins;

	for(int i = 0; i < M; i++) {
		vector<int> buckets[256];
		for(int j = 1; j <= N; j++) {
			int w = dna[j][i];
			buckets[w].push_back(j);
		}
		const char* R = "ACGT";
		for (int ii = 0; ii < 4; ii++) {
			auto& A = buckets[R[ii]];
			W a, b;
			a.side = {A.begin(), A.end()};
			for(int iii = ii + 1; iii < 4; iii++) {
				auto& B = buckets[R[iii]];
				b.side.insert(B.begin(), B.end());
			}
			a.c();
			b.c();
			if(a.side.empty() or b.side.empty())
				continue;
			bins.push_back({a, b});
		}
	}

	for (int i = 1; i <= N; i++) {
		H needed = 0;

		for(int j = 1; j <= N; j++) {
			if(i == j) continue;
			needed = (needed + coef[j] * K) & P2;
		}

		H T = 0;

		for(auto p : bins) {
			if(p.first.side.find(i) != p.first.side.end()) {
				T += p.second.hash;
			}else if(p.second.side.find(i) != p.second.side.end()) {
				T += p.first.hash;
			}
			T &= P2;
		}

		if(T == needed) {
			cout << i << '\n';
			return 0;
		}
	}
	return 0;
}

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

genetics.cpp: In function 'int main()':
genetics.cpp:51:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |    auto& A = buckets[R[ii]];
      |                      ~~~~^
genetics.cpp:55:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |     auto& B = buckets[R[iii]];
      |                       ~~~~~^

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