Submission #1206686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206686		vux2code	Genetics (BOI18_genetics)	C++20	100 / 100	795 ms	18324 KiB

genetics

// Src : Vux2Code
/* Note :
    
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

#define fi first
#define se second

#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front

#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}

template<typename T>
using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))

#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())

const ll maxN = 41e2 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;

void maxi(ll &x, ll y) { x = max(x, y); }
void mini(ll &x, ll y) { x = min(x, y); }

/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;

/* ---------BITMASK-------- */
// ll count(ll x) { return __builtin_popcountll(x); }
// ll fst(ll x) { return 63 - __builtin_clzll(x); }
// ll last(ll x) { return __builtin_ctzll(x); }
// bool bit(ll x, ll y) { return ((x >> y) & 1); }

ll t = 1;

ll n, m, k, w [maxN], sumw, sum [maxN];
char a [maxN] [maxN];
map <char, ll> mp [maxN];

void solve() {
    cin >> n >> m >> k;
    forinc (i, 1, n) {
        forinc (j, 1, m) {
            cin >> a [i] [j];
        }
    }
    random_device rd; 
    mt19937 gen (124523);
    uniform_int_distribution<> distr (1, INT_MAX);
    forinc (i, 1, n) {
        w [i] = distr (gen);
        sumw += w [i];
    }
    forinc (i, 1, n) {
        forinc (j, 1, m) {
            mp [j] [a [i] [j]] += w [i];
        }
    }
    forinc (i, 1, n) {
        forinc (j, 1, m) {
            for (pll k : mp [j]) {
                if (k. fi != a [i] [j]) sum [i] += k. se;
            }
        }
    }
    forinc (i, 1, n) {
        if (sum [i] == k * (sumw - w [i])) {
            cout << i;
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // #define TASK "E:/Code/CP/task"
    // if (fopen (TASK".inp", "r")) {
    //     freopen (TASK".inp", "r", stdin);
    //     freopen (TASK".out", "w", stdout);
    // }
    // cin >> t;
    while (t--) solve();
}

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