Submission #547423

#	Time	Username	Problem	Language	Result	Execution time	Memory
547423		Olympia	Genetics (BOI18_genetics)	C++17	27 / 100	2093 ms	4148 KiB

genetics

#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
vector<vector<int>> adj;
vector<int> color;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M, K;
    cin >> N >> M >> K;
    string arr[N];
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    vector<pair<int,int>> blocks;
    int sq = sqrt(N);
    for (int i = 0; i < sq; i++) {
        blocks.push_back({i * sq, i * sq + sq - 1});
    }
    blocks.back().second = N - 1;
    int id[N];
    map<char,int> myMap;
    myMap['A'] = 0, myMap['C'] = 1, myMap['G'] = 2, myMap['T'] = 3;
    int oc[blocks.size()][M][4];
    for (int i = 0; i < blocks.size(); i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 4; k++) {
                oc[i][j][k] = 0;
            }
        }
    }
    for (int i = 0; i < blocks.size(); i++) {
        for (int j = blocks[i].first; j <= blocks[i].second; j++) {
            id[j] = i;
            for (int k = 0; k < M; k++) {
                oc[i][k][myMap[arr[j][k]]]++;
            }
        }
    }
    set<int> pos;
    for (int i = 0; i < N; i++) {
        pos.insert(i);
    }
    for (int i = 0; i < N; i++) {
        for (int index = 0; index < blocks.size(); index++) {
            int tot = 0;
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < 4; k++) {
                    if (k != myMap[arr[i][j]]) {
                        tot += oc[index][j][k];
                    }
                }
            }
            if (tot != (blocks[index].second - blocks[index].first + 1 - (index == id[i])) * K) {
                pos.erase(i);
                break;
            }
        }
    }
    for (int j: pos) {
        bool fine = true;
        for (int i = 0; i < N; i++) {
            if (i == j) continue;
            int cntr = 0;
            for (int k = 0; k < M; k++) {
                cntr += (arr[j][k] != arr[i][k]);
            }
            if (cntr != K) {
                fine = false;
                break;
            }
        }
        if (fine) {
            cout << j + 1;
            exit(0);
        }
    }
}

Compilation message (stderr)

genetics.cpp:15: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   15 | #pragma GCC optimization ("O3")
      | 
genetics.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("unroll-loops")
      | 
genetics.cpp: In function 'int main()':
genetics.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < blocks.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
genetics.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < blocks.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
genetics.cpp:59:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int index = 0; index < blocks.size(); index++) {
      |                             ~~~~~~^~~~~~~~~~~~~~~

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