QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96582#5603. Three DicePetroTarnavskyi#WA 79ms3624kbC++172.2kb2023-04-14 16:08:062023-04-14 16:08:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-14 16:08:08]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:3624kb
  • [2023-04-14 16:08:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#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 MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

bool bad[47][47];
bool good[1 << 19];
char cha[47];

void restore(int a, int b, int c)
{
	VI v = {a, b, c};
	FOR(j, 0, 3)
	{
		FOR(i, 0, 18)
		{
			if (v[j] & (1 << i))
				cout << cha[i];
		}
		cout << ' ';
	} 
	cout << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	map<char, int> alph;
	vector<string> vs; 
	FOR(i, 0, n)
	{
		string s;
		cin >> s;
		vs.PB(s);
		FOR(j, 0, 3) alph[s[j]] = 0;
	}
	if (SZ(alph) > 18)
	{
		cout << -1 << '\n';
	}
	int jj = 0;
	while (SZ(alph) < 18)
	{
		alph['a' + jj++] = 0;
	}
	jj = 0;
	for (auto& [c, v] : alph)
	{
		cha[jj] = c;
		v = jj++;
	}
	FOR(i, 0, n)
	{
		int a = alph[vs[i][0]];
		int b = alph[vs[i][1]];
		int c = alph[vs[i][2]];
		bad[a][b] = bad[b][a] = 1;
		bad[a][c] = bad[c][a] = 1;
		bad[c][b] = bad[b][c] = 1;
	}
	FOR(ms, 0, 1 << 18)
	{
		if (__builtin_popcount(ms) == 6)
		{
			VI bts;
			FOR(j, 0, 18)
			{
				if (ms & (1 << j)) bts.PB(j);
			}
			good[ms] = 1;
			FOR(j, 0, 6) FOR(k, 0, 6) good[ms] &= !bad[bts[j]][bts[k]];
		}
		if (__builtin_popcount(ms) == 12)
		{
			int x = ms;
			while (x)
			{
				if (__builtin_popcount(x) == 6)
				{
					good[ms] |= good[x] & good[x ^ ms];
				}
				x = ms & (x - 1);
			}
		}
		if (__builtin_popcount(ms) == 18)
		{	
			int x = ms;
			while (x)
			{
				if (__builtin_popcount(x) == 6)
				{
					if (good[x] & good[x ^ ms])
					{
						int y = x ^ ms;
						while (y)
						{
							if (__builtin_popcount(y) == 6)
							{
								if (good[y] & good[x ^ y ^ ms])
								{
									restore(x, y, x ^ y ^ ms);
									return 0;
								}
							}
							y = (ms ^ x) & (y - 1);
						}
					}
				}
				x = ms & (x - 1);
			}
		}
	}
	cout << 0 << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 79ms
memory: 3588kb

input:

3
lad
fin
sly

output:

dmnopy ahijks bcefgl 

result:

ok correct

Test #2:

score: 0
Accepted
time: 78ms
memory: 3548kb

input:

1
dad

output:

0

result:

ok impossible

Test #3:

score: 0
Accepted
time: 75ms
memory: 3592kb

input:

11
aft
cog
far
irk
kit
yes
tau
rag
own
uke
via

output:

fgiuwy deortv abckns 

result:

ok correct

Test #4:

score: 0
Accepted
time: 74ms
memory: 3624kb

input:

20
aah
aal
aas
aba
abo
abs
aby
ace
act
add
ado
ads
adz
aff
aft
aga
age
ago
aha
aid

output:

0

result:

ok impossible

Test #5:

score: -100
Wrong Answer
time: 76ms
memory: 3540kb

input:

23
abc
acb
bac
bca
cab
cba
abd
adb
bad
bda
dab
dba
acd
adc
cad
cda
dac
dca
fgh
ijk
lmn
opq
rst

output:

-1
0

result:

wrong answer ! got a dice, when there's actually no solution