Submission #950623

#	Time	Username	Problem	Language	Result	Execution time	Memory
950623		Nhoksocqt1	Mutating DNA (IOI21_dna)	C++17	100 / 100	57 ms	9912 KiB

dna

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

string s, t;
int sumS[MAXN][3], sumT[MAXN][3], sum[MAXN][3][3], cnt[3], strLen;
bool check_sub3;

void init(string _S, string _T) {
    strLen = sz(_S);
    s = '^' + _S;
    t = '^' + _T;

    check_sub3 = 1;
    for (int i = 1; i <= strLen; ++i) {
        s[i] = (s[i] != 'A') + (s[i] == 'C');
        t[i] = (t[i] != 'A') + (t[i] == 'C');
        check_sub3 &= (max(s[i], t[i]) < 2);
        for (int j = 0; j < 3; ++j) {
            sumS[i][j] = sumS[i - 1][j], sumT[i][j] = sumT[i - 1][j];
            for (int k = 0; k < 3; ++k)
                sum[i][j][k] = sum[i - 1][j][k];
        }

        ++sumS[i][s[i]], ++sumT[i][t[i]];
        ++sum[i][s[i]][t[i]];
    }
}

int sub1(int l, int r) {
    cnt[0] = cnt[1] = cnt[2] = 0;
    for (int i = l; i <= r; ++i)
        ++cnt[s[i]], --cnt[t[i]];

    if(cnt[0] != 0 || cnt[1] != 0 || cnt[2] != 0)
        return -1;

    map<array<int, 3>, int> dist;
    array<int, 3> startNode, endNode;
    for (int i = 0; i < 3; ++i)
        startNode[i] = endNode[i] = -1;

    for (int i = l; i <= r; ++i) {
        startNode[i - l] = s[i];
        endNode[i - l] = t[i];
    }

    queue<array<int, 3>> qu;
    qu.push(startNode);
    dist[startNode] = 1;

    int szNow(r - l + 1);
    while(sz(qu)) {
        array<int, 3> p(qu.front());
        qu.pop();

        int distNow(dist[p]);
        if(p == endNode)
            return distNow - 1;

        for (int u = 0; u < szNow; ++u) {
            for (int v = u + 1; v < szNow; ++v) {
                swap(p[u], p[v]);
                if(dist.find(p) == dist.end()) {
                    dist[p] = distNow + 1;
                    qu.push(p);
                }

                swap(p[u], p[v]);
            }
        }
    }

    return -1;
}

int sub3(int l, int r) {
    return sum[r][0][1] - sum[l - 1][0][1];
}

int magicFunc(int l, int r) {
    int cnt[3][3];
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j)
            cnt[i][j] = sum[r][i][j] - sum[l - 1][i][j];
    }

    int res(0);
    for (int i = 0; i < 3; ++i) {
        for (int j = i + 1; j < 3; ++j) {
            int tmp = min(cnt[i][j], cnt[j][i]);
            cnt[i][j] -= tmp, cnt[j][i] -= tmp;
            res += tmp;
        }
    }

    int sum(0);
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            sum += (i != j) * cnt[i][j];
        }
    }

    assert(sum % 3 == 0);
    return res + sum / 3 * 2;
}

int get_distance(int l, int r) {
    ++l, ++r;

    for (int k = 0; k < 3; ++k) {
        if(sumT[r][k] - sumT[l - 1][k] != sumS[r][k] - sumS[l - 1][k])
            return -1;
    }

    if(r - l <= 2)
        return sub1(l, r);

    if(check_sub3)
        return sub3(l, r);

    return magicFunc(l, r);
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "dna"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    string s, t;
    cin >> s >> t;

    init(s, t);
    int numQuery;
    cin >> numQuery;
    for (int t = 0; t < numQuery; ++t) {
        int x, y;
        cin >> x >> y;
        cout << "ANSWER FOR " << x << ' ' << y << ": " << get_distance(x, y) << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:43:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |         ++sumS[i][s[i]], ++sumT[i][t[i]];
      |                       ^
dna.cpp:43:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |         ++sumS[i][s[i]], ++sumT[i][t[i]];
      |                                        ^
dna.cpp:44:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |         ++sum[i][s[i]][t[i]];
      |                      ^
dna.cpp:44:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |         ++sum[i][s[i]][t[i]];
      |                            ^
dna.cpp: In function 'int sub1(int, int)':
dna.cpp:51:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |         ++cnt[s[i]], --cnt[t[i]];
      |                   ^
dna.cpp:51:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |         ++cnt[s[i]], --cnt[t[i]];
      |                                ^

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