Submission #147790

#	Time	Username	Problem	Language	Result	Execution time	Memory
147790		gina (#201)	Get Hundred Points! (FXCUP4_hundred)	C++17	100 / 100	9 ms	384 KiB

hundred

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

string solve(int An, int Bn, char A, char B) {
	string ans;
	for(int i = 0; i < 100; i++) ans.push_back(B);
	if(An == 0) return ans;

	int res[100];
	string s;
	for(int i = 0; i < An - 1; i++) s.push_back(A);
	for(int i = An - 1; i < 100; i++) s.push_back(B);
	for(int i = 50; i < 100; i++) {
		s[i] = A;
		res[i] = Mark(s);
		s[i] = B;
	}
	int mn = 100, mx = 0;
	for(int i = 50; i < 100; i++) {
		mn = min(mn, res[i]);
		mx = max(mx, res[i]);
	}
	for(int i = 50; i < 100; i++) if(res[i] > mn) ans[i] = A;
	if(mn == mx && res[50] == 2) for(int i = 50; i < 100; i++) ans[i] = A;

	for(int i = 0; i < Bn + 1; i++) s[i] = B;
	for(int i = Bn + 1; i < 100; i++) s[i] = A;
	for(int i = 0; i < 50; i++) {
		s[i] = A;
		res[i] = Mark(s);
		s[i] = B;
	}
	mn = 100, mx = 0;
	for(int i = 0; i < 50; i++) {
		mn = min(mn, res[i]);
		mx = max(mx, res[i]);
	}
	for(int i = 0; i < 50; i++) if(res[i] > mn) ans[i] = A;
	if(mn == mx && res[0] == 2) for(int i = 0; i < 50; i++) ans[i] = A;
	return ans;
}

string solve2(int An, int Bn, char A, char B) {
	return An < Bn ? solve(An, Bn, A, B) : solve(Bn, An, B, A);
}

string solve3(int An, int Bn, int Cn, char A, char B, char C) {
	int res[3][100];
	string s;

	for(int i = 0; i < Cn; i++) s.push_back(C);
	for(int i = Cn; i < Cn + An - 1; i++) s.push_back(A);
	for(int i = Cn + An - 1; i < 99; i++) s.push_back(B);
	s.push_back(C);
	for(int i = 0; i < 33; i++) {
		s[i] = A;
		res[0][i] = Mark(s);
		s[i] = C;
	}

	for(int i = 0; i < An - 1; i++) s[i] = A;
	if(An + Bn - 1 <= 32) {
		for(int i = An - 1; i < An + Bn - 1; i++) s[i] = B;
		for(int i = An + Bn - 1; i < 100; i++) s[i] = C;
	}
	else {
		for(int i = An - 1; i < 32; i++) s[i] = B;
		for(int i = 32; i < 33 + Cn; i++) s[i] = C;
		for(int i = 33 + Cn; i < 100; i++) s[i] = B;
	}
	for(int i = 32; i < 66; i++) {
		s[i] = A;
		res[1][i] = Mark(s);
		s[i] = C;
	}

	for(int i = 0; i < An - 1; i++) s[i] = A;
	for(int i = An - 1; i < An + Bn - 1; i++) s[i] = B;
	for(int i = An + Bn - 1; i < 100; i++) s[i] = C;
	for(int i = 65; i < 98; i++) {
		s[i] = A;
		res[2][i] = Mark(s);
		s[i] = C;
	}

	int num[100];
	for(int i = 0; i < 33; i++) num[i] = res[0][i];
	for(int i = 33; i < 66; i++) num[i] = num[i - 1] + res[1][i] - res[1][i - 1];
	for(int i = 66; i < 98; i++) num[i] = num[i - 1] + res[2][i] - res[2][i - 1];

	//for(int i = 0; i < 100; i++) printf("%d ", num[i] - num[0]);
	//printf("\n");

	int mn = 100, mx = 0;
	for(int i = 0; i < 98; i++) {
		mn = min(mn, num[i]);
		mx = max(mx, num[i]);
	}

	string ans;
	if(mn == mx) for(int i = 0; i < 98; i++) ans.push_back(C);
	else if(mn == mx - 1) for(int i = 0; i < 98; i++) ans.push_back(num[i] == mx ? B : C);
	else for(int i = 0; i < 98; i++) ans.push_back(num[i] == mx ? A : (num[i] == mn ? C : B));

	//printf("%s\n", s0.c_str());

	int a, b, c;
	for(int i = 0; i < 98; i++) {
		if(ans[i] == A) a++;
		else if(ans[i] == B) b++;
		else c++;
	}

	if(An - a == 2) {
		ans.push_back(A);
		ans.push_back(A);
	}
	else if(Bn - b == 2) {
		ans.push_back(B);
		ans.push_back(B);
	}
	else if(Cn - c == 2) {
		ans.push_back(C);
		ans.push_back(C);
	}
	else {
		//printf("%d, %d, %d\n", An, Bn, Cn);
		//printf("%c, %c, %c\n", A, B, C);
		int cnt = 0;
		s[0] = A;
		for(int i = 1; i < Cn; i++) s[i] = C;
		for(int i = Cn; i < Cn + An - 1; i++) s[i] = A;
		for(int i = Cn + An - 1; i < 98; i++) s[i] = B;
		for(int i = 0; i < 98; i++) if(s[i] == ans[i]) cnt++;
		//printf("res = %d, cnt = %d\n", res[0][0], cnt);
		//cout << "ans = " << ans << "\n";
		//cout << "s   = " << s << "\n";
		if(Cn - c == 0) {
			if(cnt == res[0][0]) {
				ans.push_back(A);
				ans.push_back(B);
			}
			else {
				ans.push_back(B);
				ans.push_back(A);
			}
		}
		else if(Bn - b == 0) {
			if(cnt == res[0][0]) {
				ans.push_back(C);
				ans.push_back(A);
			}
			else {
				ans.push_back(A);
				ans.push_back(C);
			}
		}
		else {
			if(cnt == res[0][0]) {
				ans.push_back(C);
				ans.push_back(B);
			}
			else {
				ans.push_back(B);
				ans.push_back(C);
			}
		}
	}

	return ans;
}

string GetHundredPoints(int A, int B, int C) {
	if(!A) return solve2(B, C, 'B', 'C');
	if(!B) return solve2(A, C, 'A', 'C');
	if(!C) return solve2(A, B, 'A', 'B');

	if(A <= B && B <= C) return solve3(A, B, C, 'A', 'B', 'C');
	else if(A <= C && C <= B) return solve3(A, C, B, 'A', 'C', 'B');
	else if(B <= A && A <= C) return solve3(B, A, C, 'B', 'A', 'C');
	else if(B <= C && C <= A) return solve3(B, C, A, 'B', 'C', 'A');
	else if(A <= B) return solve3(C, A, B, 'C', 'A', 'B');
	else return solve3(C, B, A, 'C', 'B', 'A');
}

Compilation message (stderr)

hundred.cpp: In function 'std::__cxx11::string solve3(int, int, int, char, char, char)':
hundred.cpp:112:9: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   else c++;
        ~^~
hundred.cpp:111:25: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   else if(ans[i] == B) b++;
                        ~^~
hundred.cpp:110:20: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(ans[i] == A) a++;
                   ~^~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67