QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#335836 | #5603. Three Dice | VeryAmazed | AC ✓ | 1ms | 3832kb | C++14 | 5.6kb | 2024-02-24 03:54:21 | 2024-02-24 03:54:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// if you end up using long double, you need to set the floating point notation to fixed, and set the percision to be very high
typedef long double ld;
// contrsuct umaps like this, unordered_map<long long, int, custom_hash> safe_map;
// FIXED_RANDOM is static so it doesn not get redeclared between function calls
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
#define INF 2001001001
#define INF2 2e18
#define MOD 1000000007
#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for(long long a = b; a < c; a++)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back
#define pf push_front
#define f first
#define s second
#define mp make_pair
#define pll pair<ll, ll>
#define pii pair<int, int>
#define tp make_tuple
// first four are north, west, east ,south
int dir1[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dir2[] = {0, 1, 0, -1, 1, -1, 1, -1};
vector<int> vec;
vector<unordered_set<int, custom_hash>> edges;
int n;
bool done;
string ans1, ans2, ans3;
void recurse(int ind, vector<int>& vec1, vector<int>& vec2, vector<int>& vec3);
bool check(vector<int> cVec);
int main() {
// apparently this does fast i/o
cin.tie(0) , ios::sync_with_stdio(0);
// use this if you read in from a file
/*
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
*/
stringstream ss;
// Do it once. Do it right.
// Read the problem statement carefully
// Plan out the steps in words on a piece of paper before implementing
// after RTE(obviously) but also WA, run valgrind!!!
//cout << fixed << setprecision(12);
// if you use ld, use the above and don't use string stream
// use instead of ceil(a, b) if a and b are positive
// (a + b - 1) / b
/*
Sol:
ok so basically first you do some preprocessing work (checking to make sure each 3 letter word has all 3 characters unique, only need 18 or less letters
picking extra letters if we need less than 18), then in theory theres only 18!/(6!^3*3!) combinations to check, but I don't know how to code that, I only
can think of a way to code a 18/(6!^3) brute force. Basically each letter in the string is assigned some number 1-3 and we can prune at any point if we go
over 6 characters assigned to a number, but you can still get like 6 letters being assigned all to 1, but then those 6 then get assigned to 3 so this method
doesn't get to divide by 3!. Then to check its 15*3, cause you can represent the 3 letter words as a graph, each node is a letter and it has edges to all the letters it can't
be on the same dice width, so then for each 6 character string, we just check all pairs.
Ok so you can actually check for validity as you do the recursion instead of doing it at the end
just whenever you assign a new char a number, go through and check it against all chars previously assigned that number to make sure there is no edge between the two characters
*/
cin >> n;
done = false;
bool works = true;
unordered_set<int, custom_hash> uset;
edges.assign(26, unordered_set<int, custom_hash>());
for(int i =0; i < n; i++){
string temp;
cin >> temp;
if(temp[0] == temp[1] || temp[1] == temp[2] || temp[0] == temp[2]) works = false;
for(int j =0; j < 3; j++){
if(uset.find(temp[j]-'a') == uset.end()){
vec.pb(temp[j]-'a');
uset.insert(temp[j]-'a');
}
for(int k =0; k < 3; k++){
if(k == j) continue;
edges[temp[j]-'a'].insert(temp[k]-'a');
edges[temp[k]-'a'].insert(temp[j]-'a');
}
}
}
/*
for(int i = 0; i < vec.size(); i++){
cout << (char)(vec[i]+'a');
}
cout << endl;
for(int i = 0; i < 26; i++){
for(auto a : edges[i]){
cout << (char)(a+'a');
}
cout << endl;
}
*/
if(uset.size() > 18) works = false;
if(!works){
cout << 0 << endl;
return 0;
}
for(int i = 0; i < 26; i++){
if(vec.size() >= 18) break;
if(uset.find(i) == uset.end()) vec.pb(i);
}
vector<int> vec1, vec2, vec3;
recurse(0, vec1, vec2, vec3);
if(!done){
cout << 0 << endl;
return 0;
}else{
cout << ans1 << " " << ans2 << " " << ans3 << endl;
}
return 0;
}
void recurse(int ind, vector<int>& vec1, vector<int>& vec2, vector<int>& vec3){
if(done) return;
if(ind == 18){
done = true;
for(int i = 0; i < 6; i++){
ans1.pb(vec1[i]+'a');
}
for(int i = 0; i < 6; i++){
ans2.pb(vec2[i]+'a');
}
for(int i = 0; i < 6; i++){
ans3.pb(vec3[i]+'a');
}
}
if(vec1.size() < 6){
vec1.pb(vec[ind]);
if(check(vec1)){
recurse(ind+1, vec1, vec2, vec3);
}
vec1.pop_back();
}
if(vec2.size() < 6){
vec2.pb(vec[ind]);
if(check(vec2)){
recurse(ind+1, vec1, vec2, vec3);
}
vec2.pop_back();
}
if(vec3.size() < 6){
vec3.pb(vec[ind]);
if(check(vec3)){
recurse(ind+1, vec1, vec2, vec3);
}
vec3.pop_back();
}
}
bool check(vector<int> cVec){
bool works = true;
int m = cVec.size();
for(int i = 0; i < m-1; i++){
if(edges[cVec[m-1]].find(cVec[i]) != edges[cVec[m-1]].end()){
works = false;
break;
}
}
return works;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
input:
3 lad fin sly
output:
lfbceg aishjk dnymop
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 dad
output:
0
result:
ok impossible
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
11 aft cog far irk kit yes tau rag own uke via
output:
ackywb fgisun torevd
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
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: 0
Accepted
time: 0ms
memory: 3564kb
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:
0
result:
ok impossible
Test #6:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
24 abc bcd cde def efg fgh ghi hij ijk jkl klm lmn mno nop opq pqr qrs rst stu tuv uvw vwx wxy xyz
output:
0
result:
ok impossible
Test #7:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
121 lax tog taj fun get jar fez own now gut gul ark fax new meg fen fog log lez gum kor leg not rug fug lag kit urn gal nam gar jew rex rin ant gam mun jam nil gem kir ilk jut ern man mon awn mig mix wag erg gor fig run nim raj fix elk nom wig gat nor jow fag jaw kaf rig fin kat rag mag won wog wan ...
output:
ltfrwm aoueiy xgjnzk
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
149 pic twa cub wag spa til two pyx pis tew vug cig pul vig pol tow tis sub pew sty eld gas pes guv bal dol lob sot sap cob ply tic taw wit bow lad gal cup cep pax lab bys sup psi pox ops tel dex veg lop vat uts ods ups wiz lit gox wud cad sod cud dev paw pac dow wig gul zax sob set lag lip doc bos ...
output:
ptbgdz iauoye cwslxv
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
97 fub tav seg box tas ski bin six syn fas sag neb sot jog gab van vug zax ban fob ons ask zit jot zin jin fiz nob jut fez beg vet sox kos gib sit sat bun bot son ifs ens but fib ins bug big sen vig tab sex zig ben sin efs kas kob nos zek nab qat xis gob guv set its bag sun veg zag uns tis sty ska n...
output:
ftgxkn uaeoiy bvsjzq
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
150 jug nit hen ant imp men ply pam pah awn jig god pal pet gan put jet dol zag tap ted lip dah lez tad pom dom dig pul hup mod edh poh dow lop old wan hap wed gin tup paw tod wiz nil ton nom tan hun hin apt mop daw pol ump noh pew pot wap hid nut map lap gun tun nam gip won nag eng wad own zit mon ...
output:
jnpdzq uieayo gthmlw
result:
ok correct
Test #11:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
259 bog ant gan urn eng pit pig dam bid nod dap rib pul ens bot dim fur ops fad ugh fag bod hes lib she spy rep rum ash mug lin mig tan het rif sop pur gap bet pal mud big dah bit gun fro arm rub dib rap fed oms bas alb aft lip mol ins fas gum sob mod end ref sib dip arf mos ems hut nor ifs bra bud ...
output:
bnpmfh oaueiy gtrdls
result:
ok correct
Test #12:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
260 bog ant gan urn eng pit pig dam bid nod dap rib pul ens bot dim fur ops fad ugh fag bod hes lib she spy rep rum ash mug lin mig tan het rif sop pur gap bet pal mud big dah bit gun fro arm rub dib rap fed oms bas alb aft lip mol ins fas gum sob mod end ref sib dip arf mos ems hut nor ifs bra bud ...
output:
0
result:
ok impossible
Test #13:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
1000 lgk nur wnm czr zuk une kob elg whc evn vlx woz mne gnp odp vkz xgz wdc npu hgk ged mwd hvx crn zcr vnp uze xbv brv bve okl bwg kno xgl oeh dec kvh nvp mpz hwc pbc ngk egz zpv zme ubx hgr xbo bgw brc rmd ubp xdc mxh hxc ebu vpz bgk dwg dve deu obp ohw ubx cxl edo zkv mbr mhe kbo zwu zwv gnk rhv...
output:
lnzbhd gumcov krwexp
result:
ok correct
Test #14:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
1000 sfp fbk nfw pfk qdk odm wgv kvt nwu mgw ucs gcq gvw kjd mda fod psu jto aqb pmg jba tja kdj usd fbs gqd ckq uod vco mkc djs sbj psj boj mws obu bau bgf qbn atu ntv ncf tof jts cmg tku fac dkf pfs pkf pqa nuw ojc svp otm sbf jwk mac vsp jbs jab dam omt udo jdo dsu joc auw tqs stf vgt cgu psu nup...
output:
sknoga fqmvuj pbwdtc
result:
ok correct
Test #15:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
1000 zjh lxd ftq xkb xkb oqt clf yce fjq ylc vqy ckv cke ovh fvx xdb qft dwl wjo kqv yei vfi tcf wjd tck ibz lck jcf qvz lzq ezx yvw jif tfq fxe vxz ekc tfi tiz ilz fjw yxj yvx hze dhe ibf ehk qzl kbc yvc oxb oil ijf vfw bkh lhd bhz dhe ybc ybh eyq dbw vxf xlz jwk zjx xkt ivd bio feh yjx ywb wkl xjd...
output:
zdfkoy jltbev hxqcwi
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
1000 epn vpq xud gjq pxr hgt ezo gfs okk ukb rne iof eko flg yzz sck qwa zks bep uzh onw nfs ram tfp ctr ahw hrz fxx jgb izx gvs afn cii vbk wzx lkb sbl dga jpi nlv eon svd ioo zas bgh zdj elm aip kmf fta pmh vwr dsj gib yjv hgx ffx tyn crf yao vqm zbm bzu cay rkt jie pgn jms cpd jhd moz ymc ogc bve...
output:
0
result:
ok impossible
Test #17:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
1000 dzq bjt xwu pwy mba ekg pyo mqc nqo xrh ptt ayg ogv uga qop olo ohw rrm ekg vwq ilv emx lld ibf hpd ffn kei wop mxx quw zgn otm fcu ehs mnl evl lsk ocr bkg bpc zzx dcm jpx yak yuc qzz ktl ifb blo ktn qpm gtb nhp pao ugp qow hgt wqi axf rjz tnl rtm nyw bmx nfe rfu wru mpw wmm wzy jgm icz szd elb...
output:
0
result:
ok impossible
Test #18:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
1000 xzy hta jca xfn hjh ige fch cdl tzj gyg qsg ebt irn lys jgs bpe zog mkv ggb wos faa arr sqy cjc bbz wld rkx hdk gob ars frk ltj dzw ilg gxs ubm edf uur yfr fkv pma tek qqe tgn wwh low fit tzz txv yhq xix mnb ner jup nrl bim iwu rgh ohv mmn utv zil wqd vee ajh jwq eau rrh bdc zzm zfk ago bwi cwi...
output:
0
result:
ok impossible