Submission #59565

#	Time	Username	Problem	Language	Result	Execution time	Memory
59565		Benq	Genetics (BOI18_genetics)	C++11	100 / 100	1075 ms	20856 KiB

genetics

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

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

ll po (ll b, ll p) { return !p?1:po(b*b%MOD,p/2)*(p&1?b:1)%MOD; }
ll inv (ll b) { return po(b,MOD-2); }

int ad(int a, int b) { return (a+b)%MOD; }
int sub(int a, int b) { return (a-b+MOD)%MOD; }
int mul(int a, int b) { return (ll)a*b%MOD; }

pi operator+(const pi& l, const pi& r) { return {ad(l.f,r.f),ad(l.s,r.s)}; }
pi operator-(const pi& l, const pi& r) { return {sub(l.f,r.f),sub(l.s,r.s)}; }
pi operator*(const pi& l, const pi& r) { return {mul(l.f,r.f),mul(l.s,r.s)}; }
pi operator*(const pi& l, const int& r) { return l*pi(r,r); }
pi operator*(const int& r, const pi& l) { return l*r; }

pi operator+=(pi& l, const pi& r) { return l = l+r; }
pi operator-=(pi& l, const pi& r) { return l = l-r; }
template<class T> pi operator*=(pi& l, const T& r) { return l = l*r; }

std::ostream& operator<<(std::ostream &strm, const pi& a) {
    strm << a.f << " " << a.s << " | ";
    return strm;
}

int N,M,K;
string S[4100];
pi hsh[4100], ans[4100], sum;

int get(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> K;
    F0R(i,N) {
        cin >> S[i];
        hsh[i] = {rand()%MOD,rand()%MOD};
        sum += hsh[i];
    }
    F0R(i,M) {
        array<pi,4> tmp = array<pi,4>();
        F0R(j,N) tmp[get(S[j][i])] += hsh[j];
        F0R(j,N) ans[j] += sum-tmp[get(S[j][i])];
    }
    F0R(i,N) if (ans[i] == K*(sum-hsh[i])) cout << i+1;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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