oj.uz

Submission #147772

# Submission time Handle Problem Language Result Execution time Memory
147772 2019-08-30T15:48:17 Z gina(#3662, imyujin) Get Hundred Points! (FXCUP4_hundred) C++17
33 / 100
 14 ms 432 KB 
#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 < 65; 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 = 64; 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 < 65; i++) num[i] = num[i - 1] + res[1][i] - res[1][i - 1];
	for(int i = 65; 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());

	for(int i = 0; i < 98; i++) {
		if(ans[i] == A) An--;
		else if(ans[i] == B) Bn--;
		else Cn--;
	}

	if(An == 2) {
		ans.push_back(A);
		ans.push_back(A);
	}
	else if(Bn == 2) {
		ans.push_back(B);
		ans.push_back(B);
	}
	else if(Cn == 2) {
		ans.push_back(C);
		ans.push_back(C);
	}
	else {
		//printf("%d, %d, %d\n", An, Bn, Cn);
		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++;
		if(Cn == 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 == 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');
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 14 ms 256 KB Output is correct
3 Correct 9 ms 256 KB Output is correct
4 Correct 7 ms 256 KB Output is correct
5 Correct 8 ms 336 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 14 ms 256 KB Output is correct
3 Correct 9 ms 256 KB Output is correct
4 Correct 7 ms 256 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Incorrect 7 ms 432 KB Output isn't correct
7 Halted 0 ms 0 KB -