CSES - HIIT Open 2017 - Results
Submission details
Task:Median string
Sender:Ace of Spades
Submission time:2017-05-27 15:12:02 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.07 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.03 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.11 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.04 sdetails
#9ACCEPTED0.05 sdetails
#10ACCEPTED0.05 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.05 sdetails
#13ACCEPTED0.07 sdetails
#14ACCEPTED0.05 sdetails
#15ACCEPTED0.07 sdetails
#16ACCEPTED0.05 sdetails
#17ACCEPTED0.05 sdetails
#18ACCEPTED0.05 sdetails
#19ACCEPTED0.04 sdetails
#20ACCEPTED0.04 sdetails
#21ACCEPTED0.07 sdetails
#22ACCEPTED0.05 sdetails
#23ACCEPTED0.04 sdetails
#24ACCEPTED0.05 sdetails
#25ACCEPTED0.07 sdetails
#26ACCEPTED0.10 sdetails
#27ACCEPTED0.08 sdetails
#28ACCEPTED0.10 sdetails
#29ACCEPTED0.11 sdetails
#30ACCEPTED0.08 sdetails
#31ACCEPTED0.09 sdetails
#32ACCEPTED0.13 sdetails
#33ACCEPTED0.10 sdetails
#34ACCEPTED0.10 sdetails
#35ACCEPTED0.08 sdetails
#36ACCEPTED0.10 sdetails
#37ACCEPTED0.12 sdetails
#38ACCEPTED0.07 sdetails
#39ACCEPTED0.11 sdetails
#40ACCEPTED0.10 sdetails
#41ACCEPTED0.07 sdetails
#42ACCEPTED0.09 sdetails
#43ACCEPTED0.08 sdetails
#44ACCEPTED0.09 sdetails
#45ACCEPTED0.09 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:50:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(a1) t[a[i]]++;
                     ^
input/code.cpp:51:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(b1) t[b[j]]++;
                     ^
input/code.cpp:52:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(c1) t[c[k]]++;
                     ^
input/code.cpp:54:23: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(a1 && t[a[i]] > 1) q = a[i];
                       ^
input/code.cpp:55:23: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(b1 && t[b[j]] > 1) q = b[j];
                       ^
input/code.cpp:56:23: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(c1 && t[c[k]] > 1) q = c[k];
                       ^
input/code.cpp:71:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(a1) t[a[i]]--;...

Code

#include <bits/stdc++.h>
using namespace std;
string dp2[51][51][51];
int dp[51][51][51];
int main() {
    for(int i = 0; i < 51; ++i) {
	for(int j = 0; j < 51; ++j) {
	    for(int k = 0; k < 51; ++k) {
		dp[i][j][k] = 1e9;
	    }
	}
    }
    string a,b,c;
    cin>>a>>b>>c;
    int an, bn, cn;
    an = a.size();
    bn = b.size();
    cn = c.size();
    int t[200] = {0};
    dp[0][0][0] = 0;
    for(int i = 0; i <= an; ++i) {
	for(int j = 0; j <= bn; ++j) {
	    for(int k = 0; k <= cn; ++k) {
		if(i < an) {
		    if(dp[i+1][j][k] > dp[i][j][k]+1) {
			dp[i+1][j][k] = dp[i][j][k]+1;
			dp2[i+1][j][k] = dp2[i][j][k];
		    }
		}
		if(j < bn) {
		    if(dp[i][j+1][k] > dp[i][j][k]+1) {
			dp[i][j+1][k] = dp[i][j][k]+1;
			dp2[i][j+1][k] = dp2[i][j][k];
		    }
		}
		if(k < cn) {
		    if(dp[i][j][k+1] > dp[i][j][k]+1) {
			dp[i][j][k+1] = dp[i][j][k]+1;
			dp2[i][j][k+1] = dp2[i][j][k];
		    }
		}
		for(int a1 = 0; a1 < 2; ++a1) {
		    for(int b1 = 0; b1 < 2; ++b1) {
			for(int c1 = 0; c1 < 2; ++c1) {
			    if(i+a1 > an || j+b1 > bn || k+c1 > cn) continue;
			    int cost = 0;
			    if(a1 == 0) ++cost;
			    if(b1 == 0) ++cost;
			    if(c1 == 0) ++cost;
			    if(a1) t[a[i]]++;
			    if(b1) t[b[j]]++;
			    if(c1) t[c[k]]++;
			    char q = 0;
			    if(a1 && t[a[i]] > 1) q = a[i];
			    if(b1 && t[b[j]] > 1) q = b[j];
			    if(c1 && t[c[k]] > 1) q = c[k];
			    if(q == 0) {
				if(a1) q = a[i];
				if(b1) q = b[j];
				if(c1) q = c[k];
			    }
			    if(a1) cost += (a[i] != q);
			    if(b1) cost += (b[j] != q);
			    if(c1) cost += (c[k] != q);
			    if(dp[i+a1][j+b1][k+c1] > dp[i][j][k] + cost) {
				dp[i+a1][j+b1][k+c1] = dp[i][j][k] + cost;
				dp2[i+a1][j+b1][k+c1] = dp2[i][j][k];
				dp2[i+a1][j+b1][k+c1].push_back(q);

			    }
			    if(a1) t[a[i]]--;
			    if(b1) t[b[j]]--;
			    if(c1) t[c[k]]--;
			}
		    }
		}
		if(i != an || j != bn || k != cn) 
		dp2[i][j][k].clear();
	    }
	}
    }
    cout<<dp2[an][bn][cn]<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
A
A
A

correct output
A

user output
A

Test 2

Verdict: ACCEPTED

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
A

user output
A

Test 3

Verdict: ACCEPTED

input
A
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
A

user output
A

Test 4

Verdict: ACCEPTED

input
A
A
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
A

user output
A

Test 5

Verdict: ACCEPTED

input
EEBAKAUUFWHXAHYEANNASFUDNDZXXL...

correct output
EGBAKBBMFTHFJHEAKDASLFHBNZGXVM...

user output
JGBBKBMLIYHFJHEZKSESLFPBNZIAVB...

Test 6

Verdict: ACCEPTED

input
BABAAAAB
BBAAAAAAB
BBBABABB

correct output
BBABAAAAB

user output
BABAAAAB

Test 7

Verdict: ACCEPTED

input
AAAAA
AAABAAA
BBAAAA

correct output
AAAAAA

user output
BAAAAA

Test 8

Verdict: ACCEPTED

input
AABAABB
ABAAAB
BBABAABA

correct output
ABABAABA

user output
BABAABB

Test 9

Verdict: ACCEPTED

input
BAABAB
BBAAABAAAA
ABAAABBB

correct output
BBAAABAB

user output
ABAAABAB

Test 10

Verdict: ACCEPTED

input
BABAB
AABABBBA
BABABBB

correct output
BABABBB

user output
BABABBB

Test 11

Verdict: ACCEPTED

input
AAABBBABBB
BABBABABB
ABBBB

correct output
AABBBABB

user output
BABBBABB

Test 12

Verdict: ACCEPTED

input
AABAAABBAA
BABAB
BBBAA

correct output
BABBAA

user output
BBBAA

Test 13

Verdict: ACCEPTED

input
BBBBBBBBA
AABABAABA
ABBBAAA

correct output
ABBBBAABA

user output
AABBBAABA

Test 14

Verdict: ACCEPTED

input
BABBBABAA
AABBBBABB
AABBBAB

correct output
AABBBABA

user output
AABBBABB

Test 15

Verdict: ACCEPTED

input
ABBBBBBB
ABBABABBA
BBBBABBBA

correct output
ABBBBABBBA

user output
ABBBBBBA

Test 16

Verdict: ACCEPTED

input
BBABABAB
BBBBBA
AABAAA

correct output
BBABABA

user output
BABABA

Test 17

Verdict: ACCEPTED

input
AAABAAAA
ABABAB
BBBBBBB

correct output
ABABABA

user output
BABABAB

Test 18

Verdict: ACCEPTED

input
BBABABA
BABAAAABAA
BABBB

correct output
BABABABA

user output
BBABABA

Test 19

Verdict: ACCEPTED

input
AABBABB
BBBBAABBBA
BAABBAA

correct output
BAABBABA

user output
BAABBBA

Test 20

Verdict: ACCEPTED

input
BBBBBAA
AAABAAAA
AAABBABB

correct output
AAABBAAA

user output
AAABBAAA

Test 21

Verdict: ACCEPTED

input
AAAABBA
ABAABA
BBABBBBBA

correct output
ABAABBA

user output
ABAABBA

Test 22

Verdict: ACCEPTED

input
BBBABAB
ABBABBBAA
ABBBAABABB

correct output
ABBBABAB

user output
ABBBABAB

Test 23

Verdict: ACCEPTED

input
BBAAA
BBABAB
ABBBBABBB

correct output
BBABAB

user output
BBABAB

Test 24

Verdict: ACCEPTED

input
AABABBBAAB
BBBABBBA
ABBAAAB

correct output
ABBABBBAAB

user output
ABBABBAAB

Test 25

Verdict: ACCEPTED

input
ABBBBBBBB
BAABAABAAA
BAAAABAAAB

correct output
BAABAABAAAB

user output
BAABABBAAB

Test 26

Verdict: ACCEPTED

input
BBDDCBBCDBAABAACBAADACABBDDABB...

correct output
BADACCBCDBADBAACBAADACBABBCABB...

user output
CADACCBCDBADBAACBAADCBABBCABBD...

Test 27

Verdict: ACCEPTED

input
ADCDADBDDDCACBCCBCACDCDBCBCDBB...

correct output
DCAADADCDACBDBBDABDCCDBCABCBAC...

user output
DCAADADCDACBDBBDABCCCDBCBCBACA...

Test 28

Verdict: ACCEPTED

input
CBCBABACDDACDCBCBBBADACDCDCBCA...

correct output
DCACBABDCABCCACBCCBCBADABCDDCC...

user output
DCACBCBDCBCACBCCBCBADBCDDCCABA...

Test 29

Verdict: ACCEPTED

input
CCBADBAACDDCBAABCADBDBDCCBCCDC...

correct output
CABCBBABBDBAAACBDDABDAABCABBDB...

user output
CABCDBABBDDCAAABDDABBDBADCABCC...

Test 30

Verdict: ACCEPTED

input
DCBDBABAADBDCDCDDDCCDACADDCCAC...

correct output
DCBABACDDBACDCBDDACAACADDCCACD...

user output
DBABACBDDBCCDCBDDACAACADDCCACD...

Test 31

Verdict: ACCEPTED

input
BCBACAADABAACACADCADCDAAACDDDD...

correct output
BCDCCBADDBBACDCADCDAADACDBDADA...

user output
BCDCCBCDDBBBCDCADCDAADACDBDADA...

Test 32

Verdict: ACCEPTED

input
ACDCDACCABADADABADDAAACBDCABBB...

correct output
ACDADACCABABACABADAABACBDCABBA...

user output
ACDADACCABABAAABADBCAACDDCABBD...

Test 33

Verdict: ACCEPTED

input
ABCCDCADCDADAADBDDBBABDACBBAAC...

correct output
BCDADCDBABDBDDCBDABDACBBAAADCA...

user output
BCDADCDDABDBDCBDABDACBBAADDCAB...

Test 34

Verdict: ACCEPTED

input
DABDBACDBADABBDDBAACCAADABDBBD...

correct output
DABDCBACADBDADCAABDBDBAACDAADA...

user output
DCBDCBAACDBDACACBDCDBABACDAADA...

Test 35

Verdict: ACCEPTED

input
BCBABDCADCBADCAABCACCBDAABBCBD...

correct output
BCBDBDCADBBBBCCABCDADBDAADBCBD...

user output
BCBDBCADBBBBCCABCDADBDAADBCBDB...

Test 36

Verdict: ACCEPTED

input
TFWRLHNANNYROWCGQJUHNIAHQTQMJF...

correct output
TFCRBHJANDNYJOCGQPJAHNIACFJCMJ...

user output
TXCRBPJENDRYJOCGQPJAHWIACSJCMJ...

Test 37

Verdict: ACCEPTED

input
HLQGBFZAPEMVFIDMBTZLKOSTCSBKPX...

correct output
HKVGBAKAWEACFIBHCMNBTALCLSTSBJ...

user output
PKAWBAUFUOFHCMBTYRWTSTJDLQPXNH...

Test 38

Verdict: ACCEPTED

input
BURAOHCWCRFABWYQTGIDCIJZGAGOQH...

correct output
BUMIHPWFBAAMWREPGDCIJIGGGQHJAJ...

user output
VUMIHPWFBAAMWRWXGPCOJSGGGVHJCP...

Test 39

Verdict: ACCEPTED

input
JHLXFPNXFCWAXXBNOOKKAAOYCAJQNC...

correct output
FHPNDFCWABLINDFGCAAFYCMJNCCHYE...

user output
ZHUNGFIWABVINHRCQUVFYCMJNEPHYX...

Test 40

Verdict: ACCEPTED

input
XPRJAEQNVMRJPRONUEBLIRWTWQLPCT...

correct output
XRIAEFBHMDICDNJEBLIJDTHQCXRNAA...

user output
XRYCEFBHMDICSNJZJUIJETHQCXRNPA...

Test 41

Verdict: ACCEPTED

input
LIFBDNCQAUIBFDBQWYQYHHIHTILAGL...

correct output
GLGNIKBDNSQAJIUDBJYFIILAGJCEAK...

user output
GLGTIKEFNSQHZIUDBJYFIILAGRMRQC...

Test 42

Verdict: ACCEPTED

input
XVRPEIHNUVILHOMUZVSDUBCCWFCUPR...

correct output
XHJPIADTKEFHOUZSDUYCBAFCAHBGEU...

user output
XHWPVTDWXEFHOUZSDUMYLBFHHQBOEI...

Test 43

Verdict: ACCEPTED

input
NVXEUOKZUBIPREENTXKZNJCKOJWSZX...

correct output
NVEUJFZJNGPJUEVTJHNJCKOAWSFZUA...

user output
FNHXHUIVZJNGPAJDLOWRZAWCKYTKRZ...

Test 44

Verdict: ACCEPTED

input
TPMZYIOLFNHUYUTQEGXKDUVWIIGPZR...

correct output
TEDBKIWELFIHKUYBOANEGDCBJIBBEZ...

user output
YEDBUIWLPTXUYWOWTGQKOIEWIFJPUR...

Test 45

Verdict: ACCEPTED

input
OPTIBHSPIKWOVIIAJSDRGAHPPSWHGZ...

correct output
BHSPICWOJIIENAGODCGAHKGDWHGCAB...

user output
GHWQYCWOKILMNAGXDCMMHKIDWHGCAB...