QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#259613 | #5603. Three Dice | qusol | RE | 0ms | 3860kb | C++14 | 1.6kb | 2023-11-21 06:53:03 | 2023-11-21 06:53:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vs = vector<string>;
const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const ld eps = 1e-9;
#define sz(c) ll((c).size())
#define pb(c) push_back(c)
#define all(c) begin(c),end(c)
#define mp make_pair
#define xx first
#define yy second
#define FOR(i,a,b) for (ll i=(a); i<(b); i++)
#define FORD(i,a,b) for (ll i=ll(b)-1; i>=(a); i--)
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })
ll adj[18][18] = {0};
map<char,ll> inds;
ll getInd(char a){
if(inds.find(a) == inds.end()) inds[a] = sz(inds);
return inds[a];
}
ll solve(ll curr, vl &cols, vl &rem){
if(curr == 18) return 1;
FOR(i,0,3){
if(rem[i] == 0) continue;
ll pos=1;
FOR(j,0,curr) if(adj[curr][j] && cols[j] == i) pos = 0;
if(!pos) continue;
cols[curr] = i; rem[i]--;
if(solve(curr+1, cols, rem)) return 1;
rem[i]++;
}
return 0;
}
int main() { cin.sync_with_stdio(0); cin.tie(0);
ll n; cin >> n;
FOR(i,0,n){
string a; cin >> a;
FOR(j,1,3) FOR(k,0,j){
if(a[j] == a[k] || getInd(a[j]) >= 18 || getInd(a[k]) >= 18){
cout << "0\n";
return 0;
}
adj[getInd(a[k])][getInd(a[j])] = 1;
adj[getInd(a[j])][getInd(a[k])] = 1;
}
}
FOR(i,'a','z'+1) if(getInd(i) == 17) break;
vl cols(18);
vl rem(3,6);
if(!solve(0, cols, rem)) cout << "0\n";
else{
vvl die(3);
for(auto [k,v] : inds){
die[cols[v]].pb(k);
}
FOR(i,0,3){
FOR(j,0,6) cout << (char) die[i][j];
cout << " ";
}
cout << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3848kb
input:
3 lad fin sly
output:
abceis fghjkl dmnopy
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
1 dad
output:
0
result:
ok impossible
Test #3:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
11 aft cog far irk kit yes tau rag own uke via
output:
fgiuwy abdkos cenrtv
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3844kb
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: 3860kb
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: 3656kb
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: -100
Runtime Error
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 ...