oj.uz

답안 #343302

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343302 2021-01-03T16:01:31 Z AmirrezaM Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 452 ms 336236 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppiii;

// vectors and Sets:
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define it iterator
#define SZ(x) (ll)((x).size())
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rend(), (c).rbegin

// pairs
#define mp make_pair
#define fr first
#define sc second

// loops
#define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
#define ROF(i , n , m) for(int (i) = (n) ; (i) >= (m) ; (i)--)
//#define FOR(n) for(int (i) = (o) ; (i) < (n) ; (i)++)
//#define ROF(n) for(int (i) = (m) ; (i) >= (0) ; (i)--)

// useful numbers
#define mod (1e9 + 7)
#define INF ((1 << 64) - 1)
#define BPT(n) pow(2,floor(log2((n))));
#define LPT(n) pow(2,ceil(log2((n))*1.0));

// execution time check and Debug
#define StartEX; clock_t startExeTime = clock();
#define EndEX; clock_t endExeTime = clock();
#define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
#define debug(x) cerr << #x << " : " << x << '\n'
#define endl "\n"

// time optimization
#define Heh ios::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O0")
#pragma GCC optimize("O1")

//Calculates b'th power of a
ll pw(int a,int b){
    ll ret = 1;
    ll mul = a;
    while(b > 0){
        if(b&1)
            ret *= mul;
        mul *= mul;
        b /= 2;
    }
    return ret;
}

//Converts s string to int
ll to_int(string s){
    ll ret = 0;
    FOR(i,0,s.size()){
        ret += pw(10,s.size()-i-1) * (ll)(s[i] - '0');
    }
    return ret;
}
int sz1 = 3, sz2 = 3;
const int MAXS = 2e6 + 100;
const int MAXN = 2e5 + 100;
int child1[MAXS][4];
int child2[MAXS][4];
int mn[MAXS] , mx[MAXS];
vc<int> ind[MAXS];
int inv[MAXN];
string s[MAXN];
void insert1(int idx , int v , int l){
    mn[v] = min(mn[v] , inv[idx]);
    mx[v] = max(mx[v] , inv[idx]);
    if(l < s[idx].size() - 1){
        if(!child1[v][s[idx][l+1]-'0']) child1[v][s[idx][l+1]-'0'] = ++sz1;
        insert1(idx , child1[v][s[idx][l+1]-'0'] , l + 1);
    }
}
void insert2(int idx , int v , int l){
    ind[v].pb(inv[idx]);
    if(l){
        if(!child2[v][s[idx][l-1]-'0']) child2[v][s[idx][l-1]-'0'] = ++sz2;
        insert2(idx , child2[v][s[idx][l-1]-'0'] , l-1);
    }
}
int search1(string& s , int node , int l){
    if(mx[node] == -1e9) return -1;
    if(l == s.size()-1) return node;
    if(child1[node][s[l+1]-'0'] == 0) return -1;
    return search1(s , child1[node][s[l+1]-'0'] , l+1);
}
int search2(string& s , int node , int l){
    if(ind[node].size() == 0) return -1;
    if(l == 0) return node;
    if(child2[node][s[l-1]-'0'] == 0) return -1;
    return search2(s , child2[node][s[l-1]-'0'] , l-1);
}
int main()
{
    Heh;
    FOR(i,0,MAXS) mn[i] = 1e9 , mx[i] = -1e9;
    int n , m;
    cin >> n >> m;
    pair<string,int> tmp[n];
    FOR(i,0,n){
        cin >> s[i];
        FOR(j,0,s[i].size()){
            if(s[i][j] == 'A') s[i][j] = '0';
            if(s[i][j] == 'C') s[i][j] = '1';
            if(s[i][j] == 'G') s[i][j] = '2';
            if(s[i][j] == 'U') s[i][j] = '3';
        }
        tmp[i].fr = s[i] , tmp[i].sc = i;
    }
    sort(tmp , tmp+n);
    FOR(i,0,n) inv[tmp[i].sc] = i , insert1(tmp[i].sc , tmp[i].fr[0] - '0' , 0) ,insert2(tmp[i].sc , tmp[i].fr[tmp[i].fr.size()-1] - '0' , tmp[i].fr.size() - 1);
    while(m--){
        string p , q;
        cin >> p >> q;
        FOR(j,0,p.size()){
            if(p[j] == 'A') p[j] = '0';
            if(p[j] == 'C') p[j] = '1';
            if(p[j] == 'G') p[j] = '2';
            if(p[j] == 'U') p[j] = '3';
        }
        FOR(j,0,p.size()){
            if(q[j] == 'A') q[j] = '0';
            if(q[j] == 'C') q[j] = '1';
            if(q[j] == 'G') q[j] = '2';
            if(q[j] == 'U') q[j] = '3';
        }
        int tmp = search1(p , p[0] - '0' , 0);
        if(tmp == -1){
            cout << 0 << endl;
            continue;
        }
        int l = mn[tmp] , r = mx[tmp];
        tmp = search2(q , q[q.size()-1] - '0' , q.size()-1);
        if(tmp == -1){
            cout << 0 << endl;
            continue;
        }
        int ans = upper_bound(all(ind[tmp]) , r) - lower_bound(all(ind[tmp]) , l);
        cout << ans << endl;
    }
    // Doesn't Ac? Read the Bottom :/
}

// stuff you should look for(Thanks Benq)
//	*** int overflow, array bounds
//	* special cases (n=1?)
//	**** do smth instead of nothing and stay organized
//	* WRITE STUFF DOWN
//	*** DON'T GET STUCK ON ONE APPROACH

Compilation message

selling_rna.cpp:38:9: warning: ISO C++11 requires whitespace after the macro name
   38 | #define StartEX; clock_t startExeTime = clock();
      |         ^~~~~~~
selling_rna.cpp:39:9: warning: ISO C++11 requires whitespace after the macro name
   39 | #define EndEX; clock_t endExeTime = clock();
      |         ^~~~~
selling_rna.cpp:40:9: warning: ISO C++11 requires whitespace after the macro name
   40 | #define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
      |         ^~~~~~
selling_rna.cpp: In function 'll to_int(std::string)':
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:67:5: note: in expansion of macro 'FOR'
   67 |     FOR(i,0,s.size()){
      |     ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:67:5: note: in expansion of macro 'FOR'
   67 |     FOR(i,0,s.size()){
      |     ^~~
selling_rna.cpp: In function 'void insert1(int, int, int)':
selling_rna.cpp:84:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if(l < s[idx].size() - 1){
      |        ~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int search1(std::string&, int, int)':
selling_rna.cpp:98:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     if(l == s.size()-1) return node;
      |        ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:111:5: note: in expansion of macro 'FOR'
  111 |     FOR(i,0,MAXS) mn[i] = 1e9 , mx[i] = -1e9;
      |     ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:115:5: note: in expansion of macro 'FOR'
  115 |     FOR(i,0,n){
      |     ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:117:9: note: in expansion of macro 'FOR'
  117 |         FOR(j,0,s[i].size()){
      |         ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:117:9: note: in expansion of macro 'FOR'
  117 |         FOR(j,0,s[i].size()){
      |         ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:126:5: note: in expansion of macro 'FOR'
  126 |     FOR(i,0,n) inv[tmp[i].sc] = i , insert1(tmp[i].sc , tmp[i].fr[0] - '0' , 0) ,insert2(tmp[i].sc , tmp[i].fr[tmp[i].fr.size()-1] - '0' , tmp[i].fr.size() - 1);
      |     ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:130:9: note: in expansion of macro 'FOR'
  130 |         FOR(j,0,p.size()){
      |         ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:130:9: note: in expansion of macro 'FOR'
  130 |         FOR(j,0,p.size()){
      |         ^~~
selling_rna.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
selling_rna.cpp:136:9: note: in expansion of macro 'FOR'
  136 |         FOR(j,0,p.size()){
      |         ^~~
selling_rna.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
selling_rna.cpp:136:9: note: in expansion of macro 'FOR'
  136 |         FOR(j,0,p.size()){
      |         ^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 69228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 452 ms 336236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 72556 KB Output is correct
2 Incorrect 75 ms 71532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 69228 KB Output isn't correct
2 Halted 0 ms 0 KB -