Submission #938090

#TimeUsernameProblemLanguageResultExecution timeMemory
938090codefoxSelling RNA Strands (JOI16_selling_rna)C++14
60 / 100
1581 ms280644 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O2") int N = 3*1e6; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int n, m; cin >> n >> m; vector<array<int, 4>> prefix(N, {-1, -1, -1, -1}); vector<array<int, 4>> suffix(N, {-1, -1, -1, -1}); vector<int> preind(N, -1); vector<int> sufind(N, -1); vector<vector<int>> pnodes(N); vector<vector<int>> snodes(N); vector<int> alph(200); alph['A'] = 0; alph['C'] = 1; alph['G'] = 2; alph['U'] = 3; vector<string> ns(n); vector<int> pind(m); vector<int> sind(m); int cp = 0; int cs = 0; int dp = 0; int ds = 0; for (int i = 0; i < n; i++) cin >> ns[i]; for (int i = 0; i < m; i++) { string a, b; cin >> a >> b; reverse(b.begin(), b.end()); int curr = 0; for (char c:a) { int next = alph[c]; if (prefix[curr][next]==-1) { prefix[curr][next] = ++cp; } curr = prefix[curr][next]; } if (preind[curr]==-1) { preind[curr] = ++dp; pind[i] = dp; } else pind[i] = preind[curr]; curr = 0; for (char c:b) { int next = alph[c]; if (suffix[curr][next]==-1) { suffix[curr][next] = ++cs; } curr = suffix[curr][next]; } if (sufind[curr] ==-1) { sufind[curr] = ++ds; sind[i] = ds; } else sind[i] =sufind[curr]; } for (int i = 0; i < n; i++) { int curr = 0; for (char c:ns[i]) { int next = alph[c]; curr = prefix[curr][next]; if (curr == -1) break; if (preind[curr]!=-1) pnodes[preind[curr]].push_back(i); } reverse(ns[i].begin(), ns[i].end()); curr = 0; for (char c:ns[i]) { int next = alph[c]; curr = suffix[curr][next]; if (curr == -1) break; if (sufind[curr]!=-1) snodes[sufind[curr]].push_back(i); } } for (int i = 0; i < m; i++) { int p1 = 0; int p2 = 0; int sol = 0; while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size()) { if (pnodes[pind[i]][p1] == snodes[sind[i]][p2]) sol++; if (pnodes[pind[i]][p1] > snodes[sind[i]][p2]) p2++; else p1++; } cout << sol << "\n"; } return 0; }

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:114:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...