oj.uz

Submission #147696

# Submission time Handle Problem Language Result Execution time Memory
147696 2019-08-30T12:23:00 Z 몰랑이(#3643, cki86201) Get Hundred Points! (FXCUP4_hundred) C++17
100 / 100
 9 ms 432 KB 
#include <bits/stdc++.h>

#include "hundred.h"
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

string res;
int pp[110]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
vector <pii> L[110];
void add_edge(int x, int y, int c) {
	// A[x] + c = A[y]
	L[x].pb(pii(c, y));
	L[y].pb(pii((3-c)%3, x));
}

string ans;
int RA, RB, RC;

void dfs(int x, int fa, int c) {
	ans[x] = 'A' + c;
	for(pii e : L[x]) if(e.Se != fa) dfs(e.Se, x, (c + e.Fi) % 3);
}

string X; int v1;
int valid() {
	int cnt[3] = {};
	rep(i, 100) cnt[ans[i] - 'A']++;
	if(cnt[0] != RA || cnt[1] != RB || cnt[2] != RC) return 0;
	int c0 = 0;
	rep(i, 100) if(ans[i] == X[i]) ++c0;
	return c0 == v1;
}

void rot() {
	rep(i, 100) ans[i] = (ans[i] - 'A' + 1) % 3 + 'A';
}

std::string GetHundredPoints(int A, int B, int C) {
	RA = A, RB = B, RC = C;
	if(A == 100) {
		rep(i, 100) res += "A";
		return res;
	}
	if(B == 100) {
		rep(i, 100) res += "B";
		return res;
	}
	if(C == 100) {
		rep(i, 100) res += "C";
		return res;
	}
	ans.resize(100);
	rep(i, A) X += "A";
	rep(i, B) X += "B";
	rep(i, C) X += "C";
	v1 = Mark(X);
	vector <pii> V;
	rep(i, 100) rep(j, i) if(X[i] != X[j]) V.emplace_back(i, j);
	rep(i, 100) pp[i] = i;
	for(pii e : V) {
		int x = e.Fi, y = e.Se;
		int px = Find(e.Fi), py = Find(e.Se);
		if(px == py) continue;
		auto vx = X;
		swap(vx[x], vx[y]);
		int del = ((X[x] - 'A') - (X[y] - 'A') + 3) % 3;
		int v2 = v1 - Mark(vx);
		if(del == 1) v2 = -v2;
		v2 = (v2 + 300) % 3;
		add_edge(y, x, v2);
		pp[px] = py;
	}
	dfs(0, -1, 0);
	if(!valid()) rot();
	if(!valid()) rot();
	return ans;
}

Subtask #1
33.0 / 33.0

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

Subtask #2
67.0 / 67.0

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