Submission #461065

#	Time	Username	Problem	Language	Result	Execution time	Memory
461065		mtxas	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	7232 KiB

dna

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <deque>
#include <cstring>
#include <math.h>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <dna.h>
/****************************************************************************
								MACROS
****************************************************************************/
#define ll long long
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define _for(a, b, c) for(int (a) = (b); (a) < (c); ++(a))
#define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); ++(a))
#define _forn(a, b, c) for(int (a) = (b); (a) > (c); (a)--)
#define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
#define turbo() cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define _fre() freopen("input.txt", "r", stdin)
#define sz(x) ((int)x.size())
#define all(a) a.begin(), a.end()
#define PI 3.141592654
#define mem(x, val) memset(x, val, sizeof(x))
#define pii pair<int, int>
#define mii map<int, int>
using namespace std;
/****************************************************************************
							STRUCTS
****************************************************************************/
/****************************************************************************
							VARIABLES
****************************************************************************/
const int maxn = 1e5+1;
int sbb[maxn], sba[maxn], sbc[maxn];
int sab[maxn], saa[maxn], sac[maxn];
int ab[maxn], ba[maxn], ac[maxn], ca[maxn], bc[maxn], cb[maxn];
/****************************************************************************
							FUNCTIONS
****************************************************************************/

/****************************************************************************
								MAIN
****************************************************************************/

void init(string a, string b){
    a = ' ' + a; b = ' ' + b; int n = sz(a) -1 ;
    _foreq(i, 1, n){
        if(a[i] == 'T') a[i] = 'B';
        if(b[i] == 'T') b[i] = 'B';
    }
    _foreq(i, 1, n){
        sbb[i] = sbb[i-1] + (b[i] == 'B');
        sba[i] = sba[i-1] + (b[i] == 'A');
        sbc[i] = sbc[i-1] + (b[i] == 'C');
        sab[i] = sab[i-1] + (a[i] == 'B');
        saa[i] = saa[i-1] + (a[i] == 'A');
        sac[i] = sac[i-1] + (a[i] == 'C');
    }
    _foreq(i, 1, n){
        ab[i] = ab[i-1] + (a[i] == 'A' && b[i] == 'B');
        ba[i] = ba[i-1] + (a[i] == 'B' && b[i] == 'A');
        ac[i] = ac[i-1] + (a[i] == 'A' && b[i] == 'C');
        ca[i] = ca[i-1] + (a[i] == 'C' && b[i] == 'A');
        bc[i] = bc[i-1] + (a[i] == 'B' && b[i] == 'C');
        cb[i] = cb[i-1] + (a[i] == 'C' && b[i] == 'B');
    }
}
int get_distance(int x, int y){
    x++; y++;
    int ans = 0;
    bool pos = 1;
    pos &= (sab[y] - sab[x-1] == sbb[y] - sbb[x-1]);
    pos &= (saa[y] - saa[x-1] == sba[y] - sba[x-1]);
    pos &= (sac[y] - sac[x-1] == sbc[y] - sbc[x-1]);
    if(!pos) return -1;

    int abps = min(ab[y] - ab[x-1], ba[y] - ba[x-1]);
    int bcps = min(bc[y] - bc[x-1], cb[y] - cb[x-1]);
    int acps = min(ac[y] - ac[x-1], ca[y] - ca[x-1]);
    ans += abps + bcps + acps;
    int ovr = max(ab[y] - ab[x-1] - abps, ba[y] - ba[x-1] - abps);
    ans += (ovr<<1);
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:26:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); ++(a))
      |                                 ^
dna.cpp:58:5: note: in expansion of macro '_foreq'
   58 |     _foreq(i, 1, n){
      |     ^~~~~~
dna.cpp:26:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); ++(a))
      |                                 ^
dna.cpp:62:5: note: in expansion of macro '_foreq'
   62 |     _foreq(i, 1, n){
      |     ^~~~~~
dna.cpp:26:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); ++(a))
      |                                 ^
dna.cpp:70:5: note: in expansion of macro '_foreq'
   70 |     _foreq(i, 1, n){
      |     ^~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16