oj.uz

Submission #38141

# Submission time Handle Problem Language Result Execution time Memory
38141 2018-01-02T04:33:23 Z funcsr Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 131640 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
#define rep(i,n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

string convert(string s) {
  string o = "";
  for (char c : s) {
    if (c == 'A') o += 'a';
    else if (c == 'G') o += 'b';
    else if (c == 'C') o += 'c';
    else o += 'd';
  }
  return o;
}
string read() {
  string s;
  cin >> s;
  return convert(s);
}

vector<int> radixSort(int p, vector<int> all, string *src) {
  vector<int> s[4] = {};
  vector<int> ret;
  for (int x : all) {
    if (src[x].size() == p) ret.pb(x);
    else s[src[x][p]-'a'].pb(x);
  }
  rep(k, 4) if (!s[k].empty()) {
    vector<int> r = radixSort(p+1, s[k], src);
    ret.insert(ret.end(), all(r));
  }
  return ret;
}

struct Trie {
  int val;
  Trie *ch[4];
  Trie() : val(0) {
    rep(k, 4) ch[k] = NULL;
  }
  int find(const char *s) {
    if (*s == '\0') return val;
    int k = *s-'a';
    if (ch[k] == NULL) return 0;
    return ch[k]->find(s+1);
  }
  void add(const char *s) {
    if (*s == '\0') {
      val++;
      return;
    }
    val++;
    int k = *s-'a';
    if (ch[k] == NULL) ch[k] = new Trie();
    ch[k]->add(s+1);
  }
  void destroy() {
    rep(k, 4) if (ch[k]) {
      ch[k]->destroy();
      delete ch[k];
    }
  }
};
struct Bucket {
  vector<string> str;
  Trie *trie;
  Bucket() {
    trie = new Trie();
  }
  void add(string s) {
    str.pb(s);
    trie->add(s.c_str());
  }
  void destroy() {
    str.clear();
    trie->destroy();
    delete trie;
  }
};

int N, Q;
string S[100000];
string Qpre[100000], Qsuf[100000];
Bucket data[200000];
int ans[100000];

bool is_prefix_of(const string &S, const string &T) {
  if (T.size() > S.size()) return false;
  rep(i, T.size()) if (T[i] != S[i]) return false;
  return true;
}

int main() {
  cin >> N >> Q;
  rep(i, N) S[i] = read();
  rep(i, Q) Qpre[i] = read(), Qsuf[i] = read();
  vector<int> Si; rep(i, N) Si.pb(i); Si = radixSort(0, Si, S);
  vector<int> Qi; rep(i, Q) Qi.pb(i); Qi = radixSort(0, Qi, Qpre);
  reverse(all(Qi));

  set<P> vs;
  rep(i, N) {
    string srev(S[Si[i]]);
    reverse(all(srev));
    data[i].add(srev);
    vs.insert(P(i, i));
  }
  int V = N;

  for (int q : Qi) {
    string &T = Qpre[q];
    int l = 0;
    while (l < N && S[Si[l]]<T) l++;
    if (l == N || !is_prefix_of(S[Si[l]], T)) continue;
    auto it = vs.lower_bound(P(l, -1));
    bool ok = false;
    while (it != vs.end() && is_prefix_of(S[Si[it->_1]], T)) {
      if (!ok) assert(it->_1 == l);
      ok = true;
      int t = it->_2;
      if (data[V].str.size() < data[t].str.size()) swap(data[V], data[t]);
      for (string s : data[t].str) data[V].add(s);
      data[t].destroy();
      it = vs.erase(it);
    }
    assert(ok);
    vs.insert(P(l, V));
    reverse(all(Qsuf[q]));
    ans[q] = data[V].trie->find(Qsuf[q].c_str());
    V++;
  }
  rep(i, Q) cout << ans[i] << "\n";
  return 0;
}

Compilation message

selling_rna.cpp: In function 'std::vector<int> radixSort(int, std::vector<int>, std::__cxx11::string*)':
selling_rna.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (src[x].size() == p) ret.pb(x);
                       ^
selling_rna.cpp: In function 'bool is_prefix_of(const string&, const string&)':
selling_rna.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for (int i=0; i<(n); i++)
                                 ^
selling_rna.cpp:100:3: note: in expansion of macro 'rep'
   rep(i, T.size()) if (T[i] != S[i]) return false;
   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27416 KB Output is correct
2 Correct 3 ms 27416 KB Output is correct
3 Correct 3 ms 27416 KB Output is correct
4 Correct 6 ms 27416 KB Output is correct
5 Correct 9 ms 27416 KB Output is correct
6 Correct 19 ms 27416 KB Output is correct
7 Correct 9 ms 27416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 131640 KB Output is correct
2 Correct 939 ms 130432 KB Output is correct
3 Correct 859 ms 130124 KB Output is correct
4 Correct 906 ms 130092 KB Output is correct
5 Correct 1049 ms 94900 KB Output is correct
6 Correct 973 ms 95744 KB Output is correct
7 Correct 576 ms 107596 KB Output is correct
8 Correct 1049 ms 131148 KB Output is correct
9 Correct 1216 ms 131016 KB Output is correct
10 Correct 513 ms 128992 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1500 ms 38804 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27416 KB Output is correct
2 Correct 3 ms 27416 KB Output is correct
3 Correct 3 ms 27416 KB Output is correct
4 Correct 6 ms 27416 KB Output is correct
5 Correct 9 ms 27416 KB Output is correct
6 Correct 19 ms 27416 KB Output is correct
7 Correct 9 ms 27416 KB Output is correct
8 Correct 636 ms 131640 KB Output is correct
9 Correct 939 ms 130432 KB Output is correct
10 Correct 859 ms 130124 KB Output is correct
11 Correct 906 ms 130092 KB Output is correct
12 Correct 1049 ms 94900 KB Output is correct
13 Correct 973 ms 95744 KB Output is correct
14 Correct 576 ms 107596 KB Output is correct
15 Correct 1049 ms 131148 KB Output is correct
16 Correct 1216 ms 131016 KB Output is correct
17 Correct 513 ms 128992 KB Output is correct
18 Execution timed out 1500 ms 38804 KB Execution timed out
19 Halted 0 ms 0 KB -