제출 #498523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498523		600Mihnea	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1571 ms	196900 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 + 7;

int decode(char ch) {
  if (ch == 'A') return 0;
  if (ch == 'G') return 1;
  if (ch == 'C') return 2;
  if (ch == 'U') return 3;
  assert(false);
}

struct TrieNode {
  TrieNode* kids[4];
  int first;
  int last;
  vector<int> guys;

  TrieNode() {
    for (int i = 0; i < 4; i++) {
      kids[i] = nullptr;
    }
  }
};

void addToTrie(TrieNode* root, string s, int index) {
  TrieNode* current = root;
  for (auto &ch : s) {
    int decoded = decode(ch);
    if (!current->kids[decoded]) {
      current->kids[decoded] = new TrieNode;
    }
    current = current->kids[decoded];
  }
  current->guys.push_back(index);
}


void prepTrie(TrieNode* root, int inverse[]) {
  int index = 0;
  function<void(TrieNode*)> dfs = [&] (TrieNode* current) {
    current->first = ++index;
    for (auto &i : current->guys) {
      inverse[i] = index;
    }
    for (int j = 0; j < 4; j++) {
      if (current->kids[j]) {
        dfs(current->kids[j]);
      }
    }
    current->last = index;
  };
  dfs(root);
}

pair<int, int> getInterval(TrieNode* root, string s) {
  TrieNode* current = root;
  for (auto &ch : s) {
    int decoded = decode(ch);
    if (!current->kids[decoded]) {
      return {1, 0};
    }
    current = current->kids[decoded];
  }
  return {current->first, current->last};
}

TrieNode* root1 = new TrieNode;
TrieNode* root2 = new TrieNode;
int x[N];
int y[N];

struct BBox {
  int xmin;
  int ymin;
  int xmax;
  int ymax;
  int index;
};

int solPrint[N];

int main() {
  bool isHome;

  isHome = true;
  isHome = false;

  if (isHome) {
    freopen ("input", "r", stdin);
  } else {
    ios::sync_with_stdio(0); cin.tie(0);
  }

  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    string s, revS;
    cin >> s;
    revS = s;
    reverse(revS.begin(), revS.end());

    addToTrie(root1, s, i);
    addToTrie(root2, revS, i);
  }

  prepTrie(root1, x);
  prepTrie(root2, y);


  vector<BBox> bboxes;

  for (int iq = 1; iq <= q; iq++) {
    string pref, suf;
    cin >> pref >> suf;

    reverse(suf.begin(), suf.end());

    auto xx = getInterval(root1, pref);
    auto yy = getInterval(root2, suf);


    if (xx.first > xx.second || yy.first > yy.second) {
      continue;
    }

    int xmin = xx.first, xmax = xx.second;
    int ymin = yy.first, ymax = yy.second;

    bboxes.push_back({xmin, ymin, xmax, ymax, iq});
  }

  /// sort(bboxes.begin(), bboxes.end());
  for (auto &bbox : bboxes) {
    int xmin = bbox.xmin, ymin = bbox.ymin;
    int xmax = bbox.xmax, ymax = bbox.ymax;
    int sol = 0;
    for (int i = 1; i <= n; i++) {
      sol += (xmin <= x[i] && x[i] <= xmax && ymin <= y[i] && y[i] <= ymax);
    }
    solPrint[bbox.index] = sol;
  }


  for (int iq = 1; iq <= q; iq++) {
    cout << solPrint[iq] << "\n";
  }


  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:92:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen ("input", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40