Submission #848344

#	Time	Username	Problem	Language	Result	Execution time	Memory
848344		vjudge1	Genetics (BOI18_genetics)	C++17	100 / 100	529 ms	53140 KiB

genetics

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define pi pair<int,int>
#define ple tuple<int,int,int>
#define fi first
#define se second
#define ii make_pair
#define isz(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define heap_max(a) priority_queue<a>
#define heap_max(a) priority_queue<a,vector<a>,greater<a>>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 10;
const int base = 311;
const int mod = 1e9 + 7;

int n, m;
string s[N];
int h[N], pw[N], k;

int ch (char a) {
    if (a == 'A') return 0;
    if (a == 'C') return 1;
    if (a == 'T') return 2;
    return 3;
}

void add (int &a, int b) {
     a += b;
     if (a >= mod) a -= mod;
}

int main () {
      file("dynamic");
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

      cin >> n >> m >> k;
      pw[0] = 1;
      for (int i = 1; i <= n; ++i) pw[i] = 1ll * pw[i - 1] * base % mod;
      vector<vector<int>> x (max(n,m)+10, vector<int>(10));
      FOR(i,1,n) {
          cin >> s[i];
          for (int j = 0; j < m; ++j) {
               add(x[j][ch(s[i][j])], pw[i]);
          }
      }
      FOR(i,1,n) {
          for (int j = 0; j < m; ++j) {
               for (int c = 0; c < 4; ++c) {
                    if (c != ch(s[i][j])) {
                         add(h[i], x[j][c]);
                    }
               }
          }
          int bad = 0;
          for (int j = 1; j <= n; ++j) {
               int more = 1ll * k * pw[j] % mod;
               if (j == i) more = 0;
               add(bad, more);
          }
          if (h[i] == bad) {
              cout << i << '\n'; exit(0);
          }
      }
}

Compilation message (stderr)

genetics.cpp:16: warning: "heap_max" redefined
   16 | #define heap_max(a) priority_queue<a,vector<a>,greater<a>>
      | 
genetics.cpp:15: note: this is the location of the previous definition
   15 | #define heap_max(a) priority_queue<a>
      | 
genetics.cpp: In function 'int main()':
genetics.cpp:4:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:47:7: note: in expansion of macro 'file'
   47 |       file("dynamic");
      |       ^~~~
genetics.cpp:4:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:47:7: note: in expansion of macro 'file'
   47 |       file("dynamic");
      |       ^~~~

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