제출 #147696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147696		몰랑이 (#201)	Get Hundred Points! (FXCUP4_hundred)	C++17	100 / 100	9 ms	432 KiB

hundred

#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 / 33
• Subtask 2: 67 / 67