Submission #777785

#	Time	Username	Problem	Language	Result	Execution time	Memory
777785		aykhn	Genetics (BOI18_genetics)	C++14	27 / 100	2060 ms	11020 KiB

genetics

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// author: aykhn

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;

#define TC int t; cin >> t; while (t--) _();
#define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_setp tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define new int32_t
#define pb push_back
#define ts to_string
#define int ll
#define fi first
#define se second
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

int dif(string &a, string &b)
{
    int cnt = 0;
    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] != b[i]) cnt++;
    }
    return cnt;
}
map<string, int> mp;

new main()
{
    OPT;
    int n, m, k;
    cin >> n >> m >> k;

    vector<string> save(n);
    vector<string> v(n);

    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        mp[v[i]] = i;
        save[i] = v[i];
    }

    int c = 0;

    while (v.size() > 1 && !c)
    {
        vector<string> nw;

        int i = rand() % v.size();

        nw.pb(v[i]);

        for (int j = 0; j < v.size(); j++)
        {
            if (i == j) continue;

            if (dif(v[i], v[j]) == k)
            {
                nw.pb(v[j]);
            }
        }

        if (v.size() == nw.size()) c++;

        v = nw;
    }

    for (int i = 0; i < v.size(); i++)
    {
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            if (dif(v[i], save[j]) == k) cnt++;
        }
        if (cnt == n - 1)
        {
            cout << mp[v[i]] + 1 << endl;
            return 0;
        }
    }
}

Compilation message (stderr)

genetics.cpp: In function 'll dif(std::string&, std::string&)':
genetics.cpp:34:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < a.length(); i++)
      |                     ~~^~~~~~~~~~~~
genetics.cpp: In function 'int32_t main()':
genetics.cpp:68:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int j = 0; j < v.size(); j++)
      |                         ~~^~~~~~~~~~
genetics.cpp:83:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~

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