oj.uz

Submission #147661

# Submission time Handle Problem Language Result Execution time Memory
147661 2019-08-30T11:23:23 Z 나라는괴물을막아봐(#3642, ainta) Get Hundred Points! (FXCUP4_hundred) C++17
33 / 100
 10 ms 384 KB 
#include "hundred.h"
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int chk[110], Par[110];
string Res;

int Find(int a) {
	if (a == Par[a])return a;
	return Par[a] = Find(Par[a]);
}

std::string GetHundredPoints(int A, int B, int C) {
	string U, S;
	U.resize(100);
	int i;
	for (i = 0; i < 100; i++) {
		chk[i] = 0;
		Par[i] = i;
		if (i < A)U[i] = 'A';
		else if (i < A + B)U[i] = 'B';
		else U[i] = 'C';
	}
	srand(1879);
	int Mx = -1;
	Res.resize(100);
	for (i = 0; i < 1; i++) {
		random_shuffle(U.begin(), U.end());
		int t = Mark(U);
		if (Mx < t) {
			Mx = t;
			S = U;
		}
	}
	int cur = Mx, s = 0;
	while (1) {
		vector<int>TA, TB, TC, T;
		for (i = 0; i < 100; i++) {
			if (!chk[i] && S[i] == 'A' && Par[i] == i)TA.push_back(i), T.push_back(i);
			if (!chk[i] && S[i] == 'B' && Par[i] == i)TB.push_back(i), T.push_back(i);
			if (!chk[i] && S[i] == 'C' && Par[i] == i)TC.push_back(i), T.push_back(i);
		}
		if (T.empty())break;
		if ((TA.empty() && TB.empty()) || (TB.empty() && TC.empty()) || (TC.empty() && TA.empty())) {
			for (i = 0; i < 100; i++) {
				if (chk[Find(i)]) {
					Res[i] = Res[Find(i)];
					chk[i] = 1;
				}
			}
			int c[3] = { A,B,C };
			vector<int>TP;
			for (i = 0; i < 100; i++) {
				if (chk[i]) {
					S[i] = Res[i];
					c[S[i] - 'A']--;
				}
				else {
					TP.push_back(i);
				}
			}
			random_shuffle(TP.begin(),TP.end());
			for (i = 0; i < c[0] + c[1] + c[2];i++) {
				if (i < c[0]) {
					S[TP[i]] = 'A';
				}
				else if (i < c[0]+c[1]) {
					S[TP[i]] = 'B';
				}
				else {
					S[TP[i]] = 'C';
				}
			}
			cur = Mark(S);
			if (cur == 100) {
				return S;
			}
			continue;
		}
		int a, b;
		while (1) {
			random_shuffle(T.begin(), T.end());
			if (S[T[0]] != S[T[1]]) {
				a = T[0];
				b = T[1];
				break;
			}
		}
		string P = S;
		swap(P[a], P[b]);
		int score = Mark(P);
		if (score - cur == 2) {
			s += 2;
			S = P;
			chk[a] = chk[b] = 1;
			Res[a] = P[a], Res[b] = P[b];
			cur = score;
		}
		else if (cur - score == 2) {
			s += 2;
			chk[a] = chk[b] = 1;
			Res[a] = S[a], Res[b] = S[b];
		}
		else if (cur == score) {
			s++;
			int cc[3] = { A,B,C };
			for (i = 0; i < 100; i++) {
				if (chk[Find(i)]) {
					cc[Res[Find(i)] - 'A']--;
				}
			}
			if (cc[S[b]-'A'] < cc[S[a]-'A']) {
				swap(a, b);
			}
			Par[b] = a;
		}
		if (cur == 100)return S;
		//printf("%d\n", s);
	}
	for (i = 0; i < 100; i++) {
		if (Find(i) != i) {
			//printf("%d %d\n", i, Find(i));
			Res[i] = Res[Find(i)];
		}
	}
	return Res;
}

Subtask #1
33.0 / 33.0

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

Subtask #2
0 / 67.0

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