Submission #1037091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037091		Raimond	Mutating DNA (IOI21_dna)	C++17	0 / 100	25 ms	3924 KiB

dna

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

#define N '\n';
#define VI <vector <int>>
#define VVI <vector <vector <int>>>  
string s, s2;

int get_distance(int x, int y){
    map<char, int> el;
    map<char, int> el2;
    for(int i = x-1; i < y; i++){
        el[s[i]]++;
        el[s2[i]]++;
    }
    
    auto x2 = el.begin();
    auto y2 = el2.begin();
    bool possible = 1;
    for(int i = x - 1; i < y; i++){
        if(x2->second != y2->second){
            possible = 0;
        }
    }
    if(!possible){
        return -1;
    }
    
    int swaps = 0;
    int alright = 0;
    while(alright == y-x){
        for(int i = x-1, alright = 0; i < y; i++, alright++){
            if(s[i] != s2[i]){
                alright--;
                bool ok = 0;
                int pos = -1;
                for(int j = i + 1; j < y; j++){
                    if(s2[j] == s[i] && s2[i] == s[j]){
                        s2[i] = s[i];
                        s2[j] = s[j];
                        swaps++;
                        ok = 1;
                        break;
                    }
                    else if(s2[j] == s[i] && pos == -1){
                        pos = j;
                    }
                }
                if(!ok){
                    if(pos != -1){
                        char a = s2[i];
                        s2[pos] = s[i]; 
                        s2[pos] = a;
                        swaps++;
                    }
                }
            }
        }
    }
    
    return swaps;
}


void init(string a, string b){
    s = a;
    s2 = b;
}

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