oj.uz

Submission #147680

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

int chk[110], Par[110], PL[110];
vector<int>E[310];


string Res;

int ss = 0;

int Find2(int a) {
	if (a == Par[a])return a;
	ss += PL[a];
	return Find2(Par[a]);
}
int Find(int a) {
	ss = 0;
	return Find2(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;
		PL[i] = 0;
		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)]-'A'+ss)%3 + 'A';
					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());
			if (T.size() == 1) {
				for (int aa = 0; aa < 3; aa++) {
					int ccc[3] = { 0 };
					for (i = 0; i < 100; i++) {
						if (Find(i) == T[0]) {
							S[i] = (aa + ss) % 3 + 'A';
						}
						ccc[S[i] - 'A']++;
					}
					if (ccc[0]==A && ccc[1]==B && ccc[2]==C && Mark(S) == 100) {
						return S;
					}
				}
			}
			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 {

			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);
			}

			if (cur == score) {
				s++;
				Par[b] = a;
				PL[b] = 0;
				int s = 0;
			}
			else if (cur - score == 1) {
				s++;
				Par[b] = a;
				int aa = S[a] - 'A';
				int bb = 3 - (S[b] - 'A') - (P[b] - 'A');
				PL[b] = (bb + 3 - aa) % 3;
			}
			else {
				s++;
				Par[b] = a;
				int aa = P[a] - 'A';
				int bb = 3 - (S[b] - 'A') - (P[b] - 'A');
				PL[b] = (bb + 3 - aa) % 3;
			}
		}
		if (cur == 100)return S;
		//printf("%d\n", s);
	}
	for (i = 0; i < 100; i++) {
		if (Find(i) != i) {
			if (chk[Find(i)]) {
				Res[i] = (Res[Find(i)] - 'A' + ss) % 3 + 'A';
				chk[i] = 1;
			}
		}
	}
	return Res;
}

Compilation message

hundred.cpp: In function 'std::__cxx11::string GetHundredPoints(int, int, int)':
hundred.cpp:148:9: warning: unused variable 's' [-Wunused-variable]
     int s = 0;
         ^

Subtask #1
33.0 / 33.0

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

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 7 ms 256 KB Output is correct
6 Correct 7 ms 256 KB Output is correct
7 Correct 7 ms 256 KB Output is correct
8 Correct 7 ms 256 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 6 ms 256 KB Output is correct
13 Correct 11 ms 384 KB Output is correct
14 Correct 8 ms 256 KB Output is correct
15 Correct 6 ms 336 KB Output is correct
16 Correct 6 ms 384 KB Output is correct