QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #295433 | #4828. Four Plus Four | ucup-team1134# | 0 | 2315ms | 34084kb | C++20 | 9.1kb | 2023-12-31 06:22:56 | 2023-12-31 06:22:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
mt19937 rng(20231234);
string SS;cin>>SS;
if(SS=="password"){
int nn;cin>>nn;
vector<string> que(nn);
for(int i=0;i<nn;i++){
cin>>que[i];
}
int A;cin>>A;
vector<string> dic(A);
for(int i=0;i<A;i++) cin>>dic[i];
shuffle(all(dic),rng);
int B;cin>>B;
set<string> SE;
for(int i=0;i<B;i++){
string X;cin>>X;
SE.insert(X);
}
set<string> Z;
map<pair<string,string>,string> deta;
map<string,vector<string>> MA;
int q=0;
for(auto S:dic){
set<string> X;
for(int i=0;i<8;i++){
if(q<18956&&si(X)>=12) break;
for(int j=0;j<8;j++){
if(q<18956&&si(X)>=12) break;
if(i==j) continue;
for(int k=0;k<8;k++){
if(q<18956&&si(X)>=12) break;
if(i==k||j==k) continue;
for(int l=0;l<8;l++){
if(q<18956&&si(X)>=12) break;
if(i==l||j==l||k==l) continue;
string T;
T+=S[i];
T+=S[j];
T+=S[k];
T+=S[l];
if(SE.count(T)) X.insert(T);
}
}
}
}
if(si(X)>=3){
vector<string> Y;
for(auto a:X) Y.push_back(a);
for(int i=0;i<si(Y);i++){
for(int j=i+1;j<si(Y);j++){
for(int k=j+1;k<si(Y);k++){
vector<string> YY={Y[i],Y[j],Y[k]};
bool ok=true;
for(int a=0;a<3;a++){
for(int b=0;b<3;b++){
if(a==b) continue;
ok&=(deta.count(mp(YY[a],YY[b]))==false);
}
}
if(ok){
MA[S]=YY;
for(int a=0;a<3;a++){
for(int b=0;b<3;b++){
if(a==b) continue;
deta[mp(YY[a],YY[b])]=S;
}
}
break;
}
}
if(MA.count(S)) break;
}
if(MA.count(S)) break;
}
if(!MA.count(S)){
for(int i=0;i<si(Y);i++){
if(!deta.count(mp(Y[i],Y[i]))){
MA[S]={Y[i]};
deta[mp(Y[i],Y[i])]=S;
break;
}
}
}
/*
assert(MA.count(S));
cout<<S<<" ";
for(auto a:MA[S]) cout<<a<<" ";
cout<<q++<<endl;
assert(MA.count(S));
*/
/*
for(auto a:X){
if(!tandoku.count(a)){
set<string> Y;Y.insert(a);
MA[S]=Y;
tandoku.insert(a);
break;
}
}
if(!MA.count(S)){
while(si(X)>3) X.erase(*X.rbegin());
MA[S]=X;
}
*/
}
}
for(auto s:que){
if(si(MA[s])==1){
cout<<MA[s][0]<<" "<<MA[s][0]<<" "<<MA[s][0]<<"\n";
}else{
for(int j=0;j<3;j++){
if(j) cout<<" ";
cout<<MA[s][j];
}
cout<<"\n";
}
}
/*
for(auto [a,b]:MA){
for(auto [c,d]:MA){
if(a==c) continue;
int cn=0;
for(auto e:b) if(d.count(e)) cn++;
if(si(b)==1){
if(si(d)==1) assert(cn==0);
}else{
if(si(d)==1){
}else{
assert(cn<=1);
}
}
}
}
cout<<si(Z)<<endl;
*/
}else{
int nn;cin>>nn;
vector<pair<string,string>> que(nn);
for(int i=0;i<nn;i++){
cin>>que[i].fi>>que[i].se;
}
int A;cin>>A;
vector<string> dic(A);
for(int i=0;i<A;i++) cin>>dic[i];
shuffle(all(dic),rng);
int B;cin>>B;
set<string> SE;
for(int i=0;i<B;i++){
string X;cin>>X;
SE.insert(X);
}
set<string> Z;
map<pair<string,string>,string> deta;
map<string,vector<string>> MA;
int q=0;
for(auto S:dic){
set<string> X;
for(int i=0;i<8;i++){
if(q<18956&&si(X)>=12) break;
for(int j=0;j<8;j++){
if(q<18956&&si(X)>=12) break;
if(i==j) continue;
for(int k=0;k<8;k++){
if(q<18956&&si(X)>=12) break;
if(i==k||j==k) continue;
for(int l=0;l<8;l++){
if(q<18956&&si(X)>=12) break;
if(i==l||j==l||k==l) continue;
string T;
T+=S[i];
T+=S[j];
T+=S[k];
T+=S[l];
if(SE.count(T)) X.insert(T);
}
}
}
}
if(si(X)>=3){
vector<string> Y;
for(auto a:X) Y.push_back(a);
for(int i=0;i<si(Y);i++){
for(int j=i+1;j<si(Y);j++){
for(int k=j+1;k<si(Y);k++){
vector<string> YY={Y[i],Y[j],Y[k]};
bool ok=true;
for(int a=0;a<3;a++){
for(int b=0;b<3;b++){
if(a==b) continue;
ok&=(deta.count(mp(YY[a],YY[b]))==false);
}
}
if(ok){
MA[S]=YY;
for(int a=0;a<3;a++){
for(int b=0;b<3;b++){
if(a==b) continue;
deta[mp(YY[a],YY[b])]=S;
}
}
break;
}
}
if(MA.count(S)) break;
}
if(MA.count(S)) break;
}
if(!MA.count(S)){
for(int i=0;i<si(Y);i++){
if(!deta.count(mp(Y[i],Y[i]))){
MA[S]={Y[i]};
deta[mp(Y[i],Y[i])]=S;
break;
}
}
}
/*
assert(MA.count(S));
cout<<S<<" ";
for(auto a:MA[S]) cout<<a<<" ";
cout<<q++<<endl;
assert(MA.count(S));
*/
/*
for(auto a:X){
if(!tandoku.count(a)){
set<string> Y;Y.insert(a);
MA[S]=Y;
tandoku.insert(a);
break;
}
}
if(!MA.count(S)){
while(si(X)>3) X.erase(*X.rbegin());
MA[S]=X;
}
*/
}
}
for(auto s:que) cout<<deta[s]<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 2315ms
memory: 34084kb
input:
password 2 password couthier 28558 aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abettals abet...
output:
pads pars paws cero chit cute
input:
keys 4 pads pars cute chit paws pads pars paws 28558 aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abet...
output:
password couthier password password
result:
ok OK
Test #2:
score: 100
Accepted
time: 2257ms
memory: 34076kb
input:
password 1 quirkier 28558 aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abettals abetters abet...
output:
keir keir keir
input:
keys 1 keir keir 28558 aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abettals abetters abettin...
output:
quirkier
result:
ok OK
Test #3:
score: 100
Accepted
time: 2243ms
memory: 34032kb
input:
password 3 aardvark aardwolf aardvark 28558 aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abet...
output:
arak dark kava afar alow draw arak dark kava
input:
keys 18 dark kava arak kava draw afar arak dark arak kava kava dark alow draw afar alow kava arak draw alow dark kava afar draw arak dark kava dark dark arak alow afar kava arak dark arak 28558 aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatise...
output:
aardvark aardvark aardwolf aardvark aardvark aardvark aardwolf aardwolf aardvark aardwolf aardvark aardwolf aardvark aardvark aardvark aardwolf aardvark aardvark
result:
ok OK
Test #4:
score: 0
Stage 1: Program answer Runtime Error
input:
password 10000 aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abettals abetters abetting abetto...
output:
arak dark kava afar alow draw agas aloe aves abas beau buss abos alan aloe aper bare beep ados anna baas alba blip clap aals abed abye abas agin bash abba able bate abet asea baas abri batt boar abas babe bias abba alit tala abbe bass ease abet acid bide abed aeon ambo ambo amia anoa abed aces anus ...