Submission #880830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880830	2023-11-30T06:29:29 Z	alicanyaz	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	9936 KB

#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ost;
#define endl "\n"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pi pair<int,int> 
#define pll pair<long long,long long>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<long long,long long>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vr vector<range<int>>
#define cd complex<double>
#define pb push_back
void frd(string s){
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}
template<typename T>
struct matrix{
    vector<T> mtx;
    T Tdef;
    int column=-1,row=-1;
    matrix()  {}
    matrix(int r,int c) {
        mtx.assign(r*c,Tdef);
        row = r;
        column = c;
    }
    matrix(int r,int c,T val){
        mtx.assign(r*c,val);
        row = r;
        column = c;
    }
    struct proxy{
        matrix *m ;
        int i;
        proxy(matrix* x , int y) : m(x) , i(y){}
        T &operator[] (int j){
            return (m->mtx[i*(m->row) + j]);
        }
    };
    proxy operator[](int i){
        return proxy(this,i);
    }
    void fill(T x){for(auto &y:mtx)y=x;}
    void fill_row(int rw,T x,int l=0,int r=-1){
        if(r==-1)r = column-1;
        for(int i=l;i<=r;i++){
            mtx[rw*row + i] = x;
        }
    }
    void fill_column(int cl,T x,int l=0,int r=-1){
        if(r == -1)r = row-1;
        for(int i=l;i<=r;i++){
            mtx[i*row + cl] = x;
        }
    }
    void inc_row(int rw,T x,int l=0,int r=-1){
        if(r==-1)r = column-1;
        for(int i=l;i<=r;i++){
            mtx[rw*row + i] += x;
        }
    }
    void inc_column(int cl,T x,int l=0,int r=-1){
        if(r == -1)r = row-1;
        for(int i=l;i<=r;i++){
            mtx[i*row + cl] +=x;
        }
    }
    int count(int rw,T x,int l=0,int r=-1){
        if(r == -1)r = column-1;
        int cnt = 0;
        for(int i=l;i<=r;i++)cnt += (mtx[rw*row + i] == x);
        return cnt;
    }
    
};
template<typename V,typename S> istream& operator >> (istream &x,pair<V,S> &p){cin >> p.first >> p.second ;return x;}
template<typename V,typename S> ostream& operator << (ostream &x,const pair<V,S> &p){cout << p.first <<" "<<p.second;return x;}
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define abs(x) ((x)>0?(x):-((x)))
#define fr(i,j) for(int i=0;i<j;i++)
#define frt(a,b,c) for(int a=b;a<c;a++)
#define fra(x,y) for(auto &x:y)
#define min(a,b) ((a)<(b)?(a):(b))
#define all(x) x.begin(),x.end()
int mlog(int x) {
    return 32 - __builtin_clz(x) - 1;
}
ll sum(ll a,ll b,ll M=1e+9+7){
    a%=M;b%=M;return (a+b)%M;
}
ll subs(ll a,ll b,ll M=1e+9+7){
    a-=b;a%=M;if(a<0)a+=M;return a;
}
ll mult(ll a,ll b,ll M=1e+9+7){
    a%=M;b%=M;return (a*b)%M;
}
ll bp(ll a,ll b,ll M=1e+9+7){
    if(b == 0)return 1;
    if(b == 1)return a;
    ll x = bp(a,b/2,M);
    x = mult(x,x,M);
    if(b%2)x=mult(x,a,M);
    return x;
}

template<typename T,size_t N>
array<T,N> operator+ (const array<T,N> &a,const array<T,N> &b){
    array<T,N> x;
    fr(i,N)x[i] = a[i] + b[i];
    return x;
}
template<typename T,size_t N>
array<T,N> operator- (const array<T,N> &a,const array<T,N> &b){
    array<T,N> x;
    fr(i,N)x[i] = a[i] - b[i];
    return x;
}

template<typename T,size_t N>
array<T,N> get(int l,int r,vector<array<T,N>> &P){
    if(l == 0)return P[r];
    return P[r]-P[l-1];
}
int in(char c){
    return (c=='A'?0:c=='C'?1:2);
}
int in2(char c,char p){
    return 3*in(c) + in(p);
}
vector<array<int,3>> cntA ,cntB;
vector<array<int,9>> sgt;

void init(string A,string B){
    fastio;
    int N = A.size();
    cntA.assign(N,array<int,3>());cntB.assign(N,array<int,3>());
    fr(i,N){
        cntA[i][in(A[i])]++;
        cntB[i][in(B[i])]++;
    }
    for(int i=1;i<N;i++){
        cntA[i] = cntA[i] + cntA[i-1];
        cntB[i] = cntB[i] + cntB[i-1];
    }
    sgt.assign(N,array<int,9>());
    fr(i,N){
        sgt[i][in2(A[i],B[i])]++;
    }
    for(int i=1;i<N;i++){
        sgt[i] = sgt[i] + sgt[i-1];
    }
}
int get_distance(int x,int y){
    if(get(x,y,cntA) != get(x,y,cntB))return -1;
    auto a = get(x,y,sgt);
    int res = 0;
    // AA AC AT CA CC CT TA TC TT
    int q = min(a[1],a[3]);res+=q;
    a[1]-=q;a[3]-=q;
    q = min(a[2],a[6]);res+=q;
    a[2]-=q;a[6]-=q;
    q = min(a[5],a[7]);res+=q;
    a[5]-=q;a[7]-=q;
    a[0]=a[4]=a[8]=0;
    int mi = INT_MIN;
    fra(t,a)mi = max(mi,t);
    res += 2*mi;
    return res;
}



/*
int32_t main(){
    fastio;
    string A = "ATACAT" , B = "ACTATA";
    init(A,B);
    //cout<<get_distance(1,3);
    cout << get_distance(0,5) <<" " << get_distance(1,3) << " " << get_distance(4,5) << " " << get_distance(3,5);
}*/

Compilation message

dna.cpp: In instantiation of 'std::array<_Tp, _Nm> operator+(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&) [with T = int; long unsigned int N = 3]':
dna.cpp:154:37:   required from here
dna.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   92 | #define fr(i,j) for(int i=0;i<j;i++)
......
  121 |     fr(i,N)x[i] = a[i] + b[i];
      |        ~~~                    
dna.cpp:121:5: note: in expansion of macro 'fr'
  121 |     fr(i,N)x[i] = a[i] + b[i];
      |     ^~
dna.cpp: In instantiation of 'std::array<_Tp, _Nm> operator+(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&) [with T = int; long unsigned int N = 9]':
dna.cpp:162:34:   required from here
dna.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   92 | #define fr(i,j) for(int i=0;i<j;i++)
......
  121 |     fr(i,N)x[i] = a[i] + b[i];
      |        ~~~                    
dna.cpp:121:5: note: in expansion of macro 'fr'
  121 |     fr(i,N)x[i] = a[i] + b[i];
      |     ^~
dna.cpp: In instantiation of 'std::array<_Tp, _Nm> operator-(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&) [with T = int; long unsigned int N = 3]':
dna.cpp:134:16:   required from 'std::array<_Tp, _Nm> get(int, int, std::vector<std::array<_Tp, _Nm> >&) [with T = int; long unsigned int N = 3]'
dna.cpp:166:20:   required from here
dna.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   92 | #define fr(i,j) for(int i=0;i<j;i++)
......
  127 |     fr(i,N)x[i] = a[i] - b[i];
      |        ~~~                    
dna.cpp:127:5: note: in expansion of macro 'fr'
  127 |     fr(i,N)x[i] = a[i] - b[i];
      |     ^~
dna.cpp: In instantiation of 'std::array<_Tp, _Nm> operator-(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&) [with T = int; long unsigned int N = 9]':
dna.cpp:134:16:   required from 'std::array<_Tp, _Nm> get(int, int, std::vector<std::array<_Tp, _Nm> >&) [with T = int; long unsigned int N = 9]'
dna.cpp:167:25:   required from here
dna.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   92 | #define fr(i,j) for(int i=0;i<j;i++)
......
  127 |     fr(i,N)x[i] = a[i] - b[i];
      |        ~~~                    
dna.cpp:127:5: note: in expansion of macro 'fr'
  127 |     fr(i,N)x[i] = a[i] - b[i];
      |     ^~
dna.cpp: In function 'void frd(std::string)':
dna.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	9428 KB	Output is correct
2	Correct	28 ms	9800 KB	Output is correct
3	Correct	27 ms	8792 KB	Output is correct
4	Correct	37 ms	9556 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	436 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	6848 KB	Output is correct
5	Correct	6 ms	7000 KB	Output is correct
6	Correct	5 ms	7004 KB	Output is correct
7	Correct	5 ms	6684 KB	Output is correct
8	Correct	5 ms	7004 KB	Output is correct
9	Correct	4 ms	7004 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	6848 KB	Output is correct
5	Correct	6 ms	7000 KB	Output is correct
6	Correct	5 ms	7004 KB	Output is correct
7	Correct	5 ms	6684 KB	Output is correct
8	Correct	5 ms	7004 KB	Output is correct
9	Correct	4 ms	7004 KB	Output is correct
10	Correct	28 ms	9552 KB	Output is correct
11	Correct	29 ms	9552 KB	Output is correct
12	Correct	34 ms	9504 KB	Output is correct
13	Correct	36 ms	9568 KB	Output is correct
14	Correct	29 ms	9820 KB	Output is correct
15	Correct	29 ms	9812 KB	Output is correct
16	Correct	30 ms	9296 KB	Output is correct
17	Correct	37 ms	9628 KB	Output is correct
18	Correct	29 ms	9868 KB	Output is correct
19	Correct	26 ms	9300 KB	Output is correct
20	Correct	28 ms	9552 KB	Output is correct
21	Correct	27 ms	9808 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	6848 KB	Output is correct
5	Correct	6 ms	7000 KB	Output is correct
6	Correct	5 ms	7004 KB	Output is correct
7	Correct	5 ms	6684 KB	Output is correct
8	Correct	5 ms	7004 KB	Output is correct
9	Correct	4 ms	7004 KB	Output is correct
10	Correct	5 ms	6492 KB	Output is correct
11	Correct	5 ms	7000 KB	Output is correct
12	Correct	5 ms	6492 KB	Output is correct
13	Correct	5 ms	6964 KB	Output is correct
14	Correct	5 ms	7000 KB	Output is correct
15	Correct	5 ms	7004 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	9428 KB	Output is correct
2	Correct	28 ms	9800 KB	Output is correct
3	Correct	27 ms	8792 KB	Output is correct
4	Correct	37 ms	9556 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	436 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	6 ms	6848 KB	Output is correct
12	Correct	6 ms	7000 KB	Output is correct
13	Correct	5 ms	7004 KB	Output is correct
14	Correct	5 ms	6684 KB	Output is correct
15	Correct	5 ms	7004 KB	Output is correct
16	Correct	4 ms	7004 KB	Output is correct
17	Correct	28 ms	9552 KB	Output is correct
18	Correct	29 ms	9552 KB	Output is correct
19	Correct	34 ms	9504 KB	Output is correct
20	Correct	36 ms	9568 KB	Output is correct
21	Correct	29 ms	9820 KB	Output is correct
22	Correct	29 ms	9812 KB	Output is correct
23	Correct	30 ms	9296 KB	Output is correct
24	Correct	37 ms	9628 KB	Output is correct
25	Correct	29 ms	9868 KB	Output is correct
26	Correct	26 ms	9300 KB	Output is correct
27	Correct	28 ms	9552 KB	Output is correct
28	Correct	27 ms	9808 KB	Output is correct
29	Correct	5 ms	6492 KB	Output is correct
30	Correct	5 ms	7000 KB	Output is correct
31	Correct	5 ms	6492 KB	Output is correct
32	Correct	5 ms	6964 KB	Output is correct
33	Correct	5 ms	7000 KB	Output is correct
34	Correct	5 ms	7004 KB	Output is correct
35	Correct	1 ms	348 KB	Output is correct
36	Correct	33 ms	8932 KB	Output is correct
37	Correct	28 ms	9552 KB	Output is correct
38	Correct	29 ms	9344 KB	Output is correct
39	Correct	29 ms	9812 KB	Output is correct
40	Correct	29 ms	9936 KB	Output is correct
41	Correct	4 ms	7004 KB	Output is correct
42	Correct	28 ms	9508 KB	Output is correct
43	Correct	29 ms	9820 KB	Output is correct
44	Correct	33 ms	9904 KB	Output is correct
45	Correct	28 ms	9300 KB	Output is correct
46	Correct	28 ms	9888 KB	Output is correct
47	Correct	28 ms	9772 KB	Output is correct

Submission #880830

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 22.0 / 22.0

Subtask #3 13.0 / 13.0

Subtask #4 28.0 / 28.0

Subtask #5 16.0 / 16.0

Subtask #1
21.0 / 21.0

Subtask #2
22.0 / 22.0

Subtask #3
13.0 / 13.0

Subtask #4
28.0 / 28.0

Subtask #5
16.0 / 16.0