QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#120476#5161. Last GuessPetroTarnavskyi#RE 2ms3868kbC++173.3kb2023-07-06 18:55:522023-07-06 18:55:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-06 18:55:54]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3868kb
  • [2023-07-06 18:55:52]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))

const int ALP = 26;
const int MAX = 1 << 10;

struct Edge {
	int u, v;
	int cap, flow;
};

vector<Edge> E;
vector<int> g[MAX];
int D[MAX], Q[MAX], P[MAX];
int N;

void addEdge(int u, int v, int cap) {
	g[u].push_back(SZ(E));
	E.push_back({u, v, cap, 0});
	g[v].push_back(SZ(E));
	E.push_back({v, u, 0, 0});
}

int bfs(int s, int t) {
	FOR(i, 0, N) {
		D[i] = -1;
	}
	D[s] = 0;
	Q[0] = s;
	int qh = 0, qt = 1;
	while (qh < qt && D[t] == -1) {
		int x = Q[qh++];
		for (int e : g[x]) {
			if (E[e].flow == E[e].cap) {
				continue;
			}
			int to = E[e].v;
			if (D[to] == -1) {
				D[to] = D[x] + 1;
				Q[qt++] = to;
			}
		}
	}
	return D[t];
}

int dfs(int x, int t, int flow) {
	if (x == t || flow == 0) {
		return flow;
	}
	for (; P[x] < SZ(g[x]); P[x]++) {
		int e = g[x][P[x]], to = E[e].v;
		if (E[e].flow == E[e].cap) {
			continue;
		}
		if (D[to] == D[x] + 1) {
			int push = dfs(to, t, min(flow, E[e].cap - E[e].flow));
			if (push > 0) {
				E[e].flow += push;
				E[e ^ 1].flow -= push;
				return push;
			}
		}
	}
	return 0;
}

int flow(int s, int t, int need) {
	int res = 0;
	while (res < need && bfs(s, t) != -1) {
		FOR(i, 0, N) {
			P[i] = 0;
		}
		while (res < need) {
			int push = dfs(s, t, 47);
			if (push == 0) {
				break;
			}
			assert(push == 1);
			res += push;
		}
	}
	assert(res == need);
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int guesses, l;
	cin >> guesses >> l;
	string ans(l, '?');
	vector<int> cnt(ALP), black(ALP);
	vector idxEdge(ALP, vector<int>(l, -2));
	while (--guesses) {
		string s, t;
		cin >> s >> t;
		vector<int> curCnt(ALP), curBlack(ALP);
		FOR(j, 0, l) {
			if (t[j] == 'G') {
				ans[j] = s[j];
			}
			if (t[j] == 'B') {
				curBlack[s[j] - 'a'] = 1;
			}
			else {
				curCnt[s[j] - 'a']++;
			}
			if (t[j] != 'G') {
				idxEdge[s[j] - 'a'][j] = -1;
			}
		}
		FOR(i, 0, ALP) {
			if (curBlack[i]) {
				cnt[i] = curCnt[i];
				black[i] = curBlack[i];
			}
			else if (!black[i]) {
				cnt[i] = max(cnt[i], curCnt[i]);
			}
		}
	}
	FOR(i, 0, l) {
		if (ans[i] != '?') {
			cnt[ans[i] - 'a']--;
		}
	}
	int s = l + ALP, t = l + ALP + 1;
	N = l + ALP + 2;
	FOR(i, 0, ALP) {
		FOR(j, 0, l) {
			if (ans[j] == '?' && idxEdge[i][j] != -1) {
				idxEdge[i][j] = SZ(E);
				addEdge(i, ALP + j, 1);
			}
		}
	}
	FOR(j, 0, l) {
		addEdge(ALP + j, t, 1);
	}
	int f = count(ALL(ans), '?');
	FOR(i, 0, ALP) {
		flow(i, t, cnt[i]);
		f -= cnt[i];
	}
	FOR(i, 0, ALP) {
		if (!black[i]) {
			addEdge(s, i, l);
		}
	}
	flow(s, t, f);
	FOR(i, 0, ALP) {
		FOR(j, 0, l) {
			if (ans[j] == '?' && idxEdge[i][j] >= 0 && E[idxEdge[i][j]].flow > 0) {
				ans[j] = char(i + 'a');
			}
		}
	}
	cout << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3488kb

input:

4 5
reply YYGBB
refer BBBGG
puppy YYGBB

output:

upper

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

2 12
aabbccddeeff GGGYGBYYYBBB

output:

aabdcbeadaaa

result:

ok 

Test #3:

score: 0
Accepted
time: 2ms
memory: 3868kb

input:

25 500
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqoqqqqqqqqqqqqqqqqqqqqqqoqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqjq...

output:

abcdefghijklmnaooprstuvwxyzaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaoaaaaaaaa...

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

24 500
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

abcdefghijklmnoapqrstuwxyzaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok 

Test #5:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

23 500
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqq...

output:

abcdefagghijklmnoprstuuuvwxyzaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok 

Test #6:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

22 500
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccoccccccccccccccccccccccccccccccccccccccccccccccccfccccccccccccccccccccccccccccccccc...

output:

aabbdefffghijklmnopqrstuvwxyzaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok 

Test #7:

score: -100
Dangerous Syscalls

input:

30 20
azzzzzzzzzzzzzzzzzzz YBBBBBBBBBBBBBBBBBBB
zazzzzzzzzzzzzzzzzzz BGBBBBBBBBBBBBBBBBBB
zzazzzzzzzzzzzzzzzzz BBYBBBBBBBBBBBBBBBBB
zzzazzzzzzzzzzzzzzzz BBBYBBBBBBBBBBBBBBBB
zzzzazzzzzzzzzzzzzzz BBBBGBBBBBBBBBBBBBBB
zzzzzazzzzzzzzzzzzzz BBBBBYBBBBBBBBBBBBBB
zzzzzzazzzzzzzzzzzzz BBBBBBYBBBBBBBBBBBBB
...

output:


result: