Code Submission Evaluation System Login

HIIT Open 2017

Start:2017-05-27 11:00:00
End:2017-05-27 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2017 - Results
History
2017-05-27 12:25:20
Task:Median string
Sender:Game of Nolife
Submission time:2017-05-27 12:25:20
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.07 / 1.00details
#2ACCEPTED0.06 / 1.00details
#3ACCEPTED0.06 / 1.00details
#4ACCEPTED0.05 / 1.00details
#5ACCEPTED0.18 / 1.00details
#6ACCEPTED0.05 / 1.00details
#7ACCEPTED0.03 / 1.00details
#8ACCEPTED0.05 / 1.00details
#9ACCEPTED0.04 / 1.00details
#10ACCEPTED0.05 / 1.00details
#11ACCEPTED0.06 / 1.00details
#12ACCEPTED0.07 / 1.00details
#13ACCEPTED0.04 / 1.00details
#14ACCEPTED0.03 / 1.00details
#15ACCEPTED0.05 / 1.00details
#16ACCEPTED0.04 / 1.00details
#17ACCEPTED0.06 / 1.00details
#18ACCEPTED0.05 / 1.00details
#19ACCEPTED0.06 / 1.00details
#20ACCEPTED0.06 / 1.00details
#21ACCEPTED0.04 / 1.00details
#22ACCEPTED0.04 / 1.00details
#23ACCEPTED0.04 / 1.00details
#24ACCEPTED0.06 / 1.00details
#25ACCEPTED0.06 / 1.00details
#26ACCEPTED0.17 / 1.00details
#27ACCEPTED0.18 / 1.00details
#28ACCEPTED0.14 / 1.00details
#29ACCEPTED0.18 / 1.00details
#30ACCEPTED0.13 / 1.00details
#31ACCEPTED0.15 / 1.00details
#32ACCEPTED0.13 / 1.00details
#33ACCEPTED0.15 / 1.00details
#34ACCEPTED0.14 / 1.00details
#35ACCEPTED0.14 / 1.00details
#36ACCEPTED0.17 / 1.00details
#37ACCEPTED0.17 / 1.00details
#38ACCEPTED0.15 / 1.00details
#39ACCEPTED0.15 / 1.00details
#40ACCEPTED0.14 / 1.00details
#41ACCEPTED0.14 / 1.00details
#42ACCEPTED0.16 / 1.00details
#43ACCEPTED0.13 / 1.00details
#44ACCEPTED0.12 / 1.00details
#45ACCEPTED0.18 / 1.00details

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

struct fro{
	int a,b,c;
	char ch;
};

int dp[55][55][55];
fro dpf[55][55][55];

void go(int a, int b, int c, int v, fro f){
	if (v<dp[a][b][c]){
		dp[a][b][c]=v;
		dpf[a][b][c]=f;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string a,b,c;
	cin>>a>>b>>c;
	int as=a.size();
	int bs=b.size();
	int cs=c.size();
	for (int i=0;i<=as;i++){
		for (int ii=0;ii<=bs;ii++){
			for (int iii=0;iii<=cs;iii++){
				dp[i][ii][iii]=1e9;
			}
		}
	}
	dp[0][0][0]=0;
	for (int i=0;i<=as;i++){
		for (int ii=0;ii<=bs;ii++){
			for (int iii=0;iii<=cs;iii++){
				int tc=dp[i][ii][iii];
				for (int j=0;j<8;j++){
					int ni=i;
					int nii=ii;
					int niii=iii;
					if ((j&1)>0&&i==as) continue;
					else if (j&1) ni=i+1;
					if ((j&2)>0&&ii==bs) continue;
					else if (j&2) nii=ii+1;
					if ((j&4)>0&&iii==cs) continue;
					else if (j&4) niii=iii+1;
					for (char ch='A';ch<='Z';ch++){
						int co=0;
						if ((j&1)>0){
							if (a[i]!=ch) co++;
						}
						else co++;
						if ((j&2)>0){
							if (b[ii]!=ch) co++;
						}
						else co++;
						if ((j&4)>0){
							if (c[iii]!=ch) co++;
						}
						else co++;
						go(ni, nii, niii, tc+co, {i, ii, iii, ch});
					}
					go(ni, nii, niii, tc+__builtin_popcount(j), {i, ii, iii, ' '});
				}
			}
		}
	}
	int be=1e9;
	int bea=0;
	int beb=0;
	int bec=0;
	for (int i=0;i<=as;i++){
		for (int ii=0;ii<=bs;ii++){
			for (int iii=0;iii<=cs;iii++){
				int ac=as-i+bs-ii+cs-iii;
				if (dp[i][ii][iii]+ac<be){
					be=dp[i][ii][iii]+ac;
					bea=i;
					beb=ii;
					bec=iii;
				}
			}
		}
	}
	string ans;
	while (bea>0||beb>0||bec>0){
// 		cout<<bea<<" "<<beb<<" "<<bec<<endl;
		if (dpf[bea][beb][bec].ch!=' ') ans+=dpf[bea][beb][bec].ch;
		int na=dpf[bea][beb][bec].a;
		int nb=dpf[bea][beb][bec].b;
		int nc=dpf[bea][beb][bec].c;
		bea=na;
		beb=nb;
		bec=nc;
	}
	reverse(ans.begin(), ans.end());
	cout<<ans<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
A
A
A
view   save

correct output
A
view   save

user output
A
view   save

Test 2

Verdict: ACCEPTED

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
A
A
view   save

correct output
A
view   save

user output
A
view   save

Test 3

Verdict: ACCEPTED

input
A
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
A
view   save

correct output
A
view   save

user output
A
view   save

Test 4

Verdict: ACCEPTED

input
A
A
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
view   save

correct output
A
view   save

user output
A
view   save

Test 5

Verdict: ACCEPTED

input
EEBAKAUUFWHXAHYEANNASFUDNDZXXL...
AQFZGVBKKVBEMTTJHESKDIULFHRZZI...
JGBFSBLBMLIYHZRMFJZVZKSESLPPBN...
view   save

correct output
EGBAKBBMFTHFJHEAKDASLFHBNZGXVM...
view   save

user output
EGBBKAMBEMHFJHEAKDASLFHBNZIAVB...
view   save

Test 6

Verdict: ACCEPTED

input
BABAAAAB
BBAAAAAAB
BBBABABB
view   save

correct output
BBABAAAAB
view   save

user output
BABAAAAB
view   save

Test 7

Verdict: ACCEPTED

input
AAAAA
AAABAAA
BBAAAA
view   save

correct output
AAAAAA
view   save

user output
AAAAA
view   save

Test 8

Verdict: ACCEPTED

input
AABAABB
ABAAAB
BBABAABA
view   save

correct output
ABABAABA
view   save

user output
ABABAAB
view   save

Test 9

Verdict: ACCEPTED

input
BAABAB
BBAAABAAAA
ABAAABBB
view   save

correct output
BBAAABAB
view   save

user output
ABAAABAB
view   save

Test 10

Verdict: ACCEPTED

input
BABAB
AABABBBA
BABABBB
view   save

correct output
BABABBB
view   save

user output
BABABBB
view   save

Test 11

Verdict: ACCEPTED

input
AAABBBABBB
BABBABABB
ABBBB
view   save

correct output
AABBBABB
view   save

user output
AABBBABB
view   save

Test 12

Verdict: ACCEPTED

input
AABAAABBAA
BABAB
BBBAA
view   save

correct output
BABBAA
view   save

user output
BBBAA
view   save

Test 13

Verdict: ACCEPTED

input
BBBBBBBBA
AABABAABA
ABBBAAA
view   save

correct output
ABBBBAABA
view   save

user output
AABBBAABA
view   save

Test 14

Verdict: ACCEPTED

input
BABBBABAA
AABBBBABB
AABBBAB
view   save

correct output
AABBBABA
view   save

user output
AABBBAB
view   save

Test 15

Verdict: ACCEPTED

input
ABBBBBBB
ABBABABBA
BBBBABBBA
view   save

correct output
ABBBBABBBA
view   save

user output
ABBBABBB
view   save

Test 16

Verdict: ACCEPTED

input
BBABABAB
BBBBBA
AABAAA
view   save

correct output
BBABABA
view   save

user output
BABABA
view   save

Test 17

Verdict: ACCEPTED

input
AAABAAAA
ABABAB
BBBBBBB
view   save

correct output
ABABABA
view   save

user output
ABABAB
view   save

Test 18

Verdict: ACCEPTED

input
BBABABA
BABAAAABAA
BABBB
view   save

correct output
BABABABA
view   save

user output
BBABABA
view   save

Test 19

Verdict: ACCEPTED

input
AABBABB
BBBBAABBBA
BAABBAA
view   save

correct output
BAABBABA
view   save

user output
BAABBAA
view   save

Test 20

Verdict: ACCEPTED

input
BBBBBAA
AAABAAAA
AAABBABB
view   save

correct output
AAABBAAA
view   save

user output
AAABBAA
view   save

Test 21

Verdict: ACCEPTED

input
AAAABBA
ABAABA
BBABBBBBA
view   save

correct output
ABAABBA
view   save

user output
ABAABBA
view   save

Test 22

Verdict: ACCEPTED

input
BBBABAB
ABBABBBAA
ABBBAABABB
view   save

correct output
ABBBABAB
view   save

user output
ABBBABAB
view   save

Test 23

Verdict: ACCEPTED

input
BBAAA
BBABAB
ABBBBABBB
view   save

correct output
BBABAB
view   save

user output
BBABAB
view   save

Test 24

Verdict: ACCEPTED

input
AABABBBAAB
BBBABBBA
ABBAAAB
view   save

correct output
ABBABBBAAB
view   save

user output
ABBABBBA
view   save

Test 25

Verdict: ACCEPTED

input
ABBBBBBBB
BAABAABAAA
BAAAABAAAB
view   save

correct output
BAABAABAAAB
view   save

user output
BAABAABAAA
view   save

Test 26

Verdict: ACCEPTED

input
BBDDCBBCDBAABAACBAADACABBDDABB...
DADBBCADDBADBADBADBBDABCABDCAD...
CADACCBCDCADBBBAACBBAACCCBABBC...
view   save

correct output
BADACCBCDBADBAACBAADACBABBCABB...
view   save

user output
BADACCBCDBADBABAACBBAACACABBCD...
view   save

Test 27

Verdict: ACCEPTED

input
ADCDADBDDDCACBCCBCACDCDBCBCDBB...
DCCACADACBCDDBBDBADBABADCCDBCA...
DAAAADCDACCDBBDABCCDDAABCBACCD...
view   save

correct output
DCAADADCDACBDBBDABDCCDBCABCBAC...
view   save

user output
DCAADADCDACBDBBDABCCCDBCBCBACA...
view   save

Test 28

Verdict: ACCEPTED

input
CBCBABACDDACDCBCBBBADACDCDCBCA...
DAACABBDCAABCCAACBCCDBCBADDBCD...
BDDCACBCBDCBCCCBCCCCBCABCDDCCC...
view   save

correct output
DCACBABDCABCCACBCCBCBADABCDDCC...
view   save

user output
DCACBABDCBCACBCCBCBADBCDDCCABA...
view   save

Test 29

Verdict: ACCEPTED

input
CCBADBAACDDCBAABCADBDBDCCBCCDC...
BBCCABBCBBABBDBCAADBDDABCDBACC...
CADCDBBBBBDCAAACCBDDABDAABBBDA...
view   save

correct output
CABCBBABBDBAAACBDDABDAABCABBDB...
view   save

user output
CABCBBABBDBAAACBDDABAABBCAABDB...
view   save

Test 30

Verdict: ACCEPTED

input
DCBDBABAADBDCDCDDDCCDACADDCCAC...
ACACCCBDDBCCACBDDADADCBADDDADC...
DBABACDDBADBBDAACAACDCCCAACBBC...
view   save

correct output
DCBABACDDBACDCBDDACAACADDCCACD...
view   save

user output
DBABACADDBCCDCBDDACAACADDCCACD...
view   save

Test 31

Verdict: ACCEPTED

input
BCBACAADABAACACADCADCDAAACDDDD...
DCDCCCBDDCBDCDCADCCBDDBBDBDADA...
BCDCCBCDDBBBBBCBDCDAADACDCBBAD...
view   save

correct output
BCDCCBADDBBACDCADCDAADACDBDADA...
view   save

user output
BCDCCAADDBBACDCADCDAADACDBDADA...
view   save

Test 32

Verdict: ACCEPTED

input
ACDCDACCABADADABADDAAACBDCABBB...
CDDACACAAABCAACABADABBAABDDDDB...
ACCADACCABBBABAAABACBCCACACABD...
view   save

correct output
ACDADACCABABACABADAABACBDCABBA...
view   save

user output
ACDADACCABABAAABADBAAACBDCABBD...
view   save

Test 33

Verdict: ACCEPTED

input
ABCCDCADCDADAADBDDBBABDACBBAAC...
BCDADCDCBDBCBDABDACBBCAAADBAAA...
BBADBCDBABDBDDCBDAADDAADAADDCA...
view   save

correct output
BCDADCDBABDBDDCBDABDACBBAAADCA...
view   save

user output
BCDADCDDABDBDCBDABDACBBAAADCAB...
view   save

Test 34

Verdict: ACCEPTED

input
DABDBACDBADABBDDBAACCAADABDBBD...
DCCDCCACCDCBCDADCAABDBDBADACDA...
DBDCBAAADBDBACACDDCDBDBABDBDDA...
view   save

correct output
DABDCBACADBDADCAABDBDBAACDAADA...
view   save

user output
DABDCBAACDBDACAABDBDBABACDAADA...
view   save

Test 35

Verdict: ACCEPTED

input
BCBABDCADCBADCAABCACCBDAABBCBD...
BCDDADBBBBCCACDADBDAADBCDDABCB...
CACCBDBCABBBBCCDBBCDDBBAADDBBB...
view   save

correct output
BCBDBDCADBBBBCCABCDADBDAADBCBD...
view   save

user output
BCBDBCADBBBBCCABCDADBDAADBCBDB...
view   save

Test 36

Verdict: ACCEPTED

input
TFWRLHNANNYROWCGQJUHNIAHQTQMJF...
FTIHRBYDSVTMVNJECPGSWQPYJQHYIQ...
DXCJBPJENDRYJASOLLFPCAHWKCCSJC...
view   save

correct output
TFCRBHJANDNYJOCGQPJAHNIACFJCMJ...
view   save

user output
TFCRBDJANDNYJOCGQPJAHNIACFJCMJ...
view   save

Test 37

Verdict: ACCEPTED

input
HLQGBFZAPEMVFIDMBTZLKOSTCSBKPX...
PKVCUBARUWFACSXTYGWNBTAPFLTNQJ...
VNZVXPAKAWJAUFUOBHCMRBSYVCRWTS...
view   save

correct output
HKVGBAKAWEACFIBHCMNBTALCLSTSBJ...
view   save

user output
PKAGBAPEUOFACMBTYGWNSTCDLKPXNH...
view   save

Test 38

Verdict: ACCEPTED

input
BURAOHCWCRFABWYQTGIDCIJZGAGOQH...
JFCLZYUMKEPWFDADMHSEPAPTZJINGW...
VTMIHPQTSFBAAVMJULWRWXGCOSSGGG...
view   save

correct output
BUMIHPWFBAAMWREPGDCIJIGGGQHJAJ...
view   save

user output
BUMIHPWFBAAMWREPGDCIJIGGGQHJCL...
view   save

Test 39

Verdict: ACCEPTED

input
JHLXFPNXFCWAXXBNOOKKAAOYCAJQNC...
FYVNDFBYLABSLINLIFGCIFYKMFOJVS...
RUCZHUZGVIWBVIMDHRCQUVFPCPMWNE...
view   save

correct output
FHPNDFCWABLINDFGCAAFYCMJNCCHYE...
view   save

user output
FHPNDFCWABLINHICGAAFYCMJNCCHYE...
view   save

Test 40

Verdict: ACCEPTED

input
XPRJAEQNVMRJPRONUEBLIRWTWQLPCT...
RZXRIREFPPPMDZNDNVWQDNIJDHQXRN...
YCWFBHCDICSHJZJUFJETHSCBONSPAH...
view   save

correct output
XRIAEFBHMDICDNJEBLIJDTHQCXRNAA...
view   save

user output
XRIAEFBHMDICDNJEBLIJETHQCXRNAA...
view   save

Test 41

Verdict: ACCEPTED

input
LIFBDNCQAUIBFDBQWYQYHHIHTILAGL...
GLGNIELKZRTINBSQJLJIUDNZRNIIUT...
GMGMTIKEFLSPHZDUBJYFFFLARRMRQC...
view   save

correct output
GLGNIKBDNSQAJIUDBJYFIILAGJCEAK...
view   save

user output
GLGNIKBDNSQAJIUDBJYFIILAGJCEAK...
view   save

Test 42

Verdict: ACCEPTED

input
XVRPEIHNUVILHOMUZVSDUBCCWFCUPR...
JOGXOJPJADTKGHUZDXYITOXAMCAHDG...
XHWWVTDWXEFBOORSRSUMYLBFBHHQBO...
view   save

correct output
XHJPIADTKEFHOUZSDUYCBAFCAHBGEU...
view   save

user output
XHJPIADUTEFHOUZDRDUBCCAFCAHBGE...
view   save

Test 43

Verdict: ACCEPTED

input
NVXEUOKZUBIPREENTXKZNJCKOJWSZX...
ONHVYUTVDSFZWJGNGPAJUVVPMHYMCK...
SPFNJIHJNXHUIVTJNJDLOWRZAWGSYT...
view   save

correct output
NVEUJFZJNGPJUEVTJHNJCKOAWSFZUA...
view   save

user output
FNHXEUIVZJNGPAJDLOPKZAJCKYTKFZ...
view   save

Test 44

Verdict: ACCEPTED

input
TPMZYIOLFNHUYUTQEGXKDUVWIIGPZR...
DVKIWQHFEIYKOYZJABOANEWDSCBJIB...
YEDBURWELMPTXUYWOCWTGZQKOIEZFJ...
view   save

correct output
TEDBKIWELFIHKUYBOANEGDCBJIBBEZ...
view   save

user output
TEDBKIWLFFEUYKOQEGAKOIEWIBBPUR...
view   save

Test 45

Verdict: ACCEPTED

input
OPTIBHSPIKWOVIIAJSDRGAHPPSWHGZ...
YHUVWOJXYEPAGOOXQNVNGNLMGGABTK...
GWWQYCWJKILMNTGXDTCMLCMMHKKIDW...
view   save

correct output
BHSPICWOJIIENAGODCGAHKGDWHGCAB...
view   save

user output
BHSPICWOJILEIAGODCGAHKGDWHGCAB...
view   save