Submission #515899

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
515899	2022-01-20 05:19:36	amunduzbaev	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	1599 ms	70604 KiB

selling_rna

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ar array
 
const int N = 2e6 + 5;
const int P = 167;
const int mod = (119 << 23) + 1;
 
signed main(){
  ios::sync_with_stdio(0); cin.tie(0);
  
  int n, m; cin>>n>>m;
  vector<string> s(n), r(n);
  vector<vector<int>> pref(n), suff(n);
  for(int i=0;i<n;i++){
    cin>>s[i]; 
  } sort(s.begin(), s.end());
  
  for(int i=0;i<n;i++){
    pref[i].resize(s[i].size());
    suff[i].resize(s[i].size());
    r[i] = s[i];
    reverse(r[i].begin(), r[i].end());
    for(int j=0;j<(int)s[i].size();j++){
      if(j) pref[i][j] = pref[i][j-1], suff[i][j] = suff[i][j-1];
      pref[i][j] = (pref[i][j] * 1ll * P + s[i][j]) % mod;
      suff[i][j] = (suff[i][j] * 1ll * P + r[i][j]) % mod;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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