QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408763#303. Guess My Word!bachbeo2007100 ✓884ms3796kbC++203.6kb2024-05-10 23:37:422024-05-10 23:37:43

Judging History

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

  • [2024-05-10 23:37:43]
  • 评测
  • 测评结果:100
  • 用时:884ms
  • 内存:3796kb
  • [2024-05-10 23:37:42]
  • 提交

answer

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const long long inf=1e18;
const int mod=998244353;
const int maxn=1005;
const int B=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;

int n,cnt,len;
string s[maxn];
bool used[maxn],cc[26];

int f(int i,int x){
    for(int j=0;j<(int)s[i].length();j++) if(s[i][j]-'A'==x) return j;
    return -1;
}

bool backtrack(int num){
    if(num<0) return true;
    if(cnt<=1) return false;

    for(int x=0;x<26;x++){
        //cout << "backtrack " << num << ' ' << x << '\n';
        if(cc[x]) continue;

        cc[x]=true;
        bool check=false;
        vector<int> del;
        for(int i=1;i<=n;i++){
            if(used[i] && f(i,x)!=-1){
                del.push_back(i);
                used[i]=false;
            }
        }
        cnt-=(int)del.size();
        if(backtrack(num-1)) check=true;
        cnt+=(int)del.size();
        for(int i:del) used[i]=true;

        if(check){
            cc[x]=false;
            continue;
        }
        for(int k=0;k<len;k++){
            del.clear();
            for(int i=1;i<=n;i++){
                if(used[i] && f(i,x)!=k){
                    del.push_back(i);
                    used[i]=false;
                }
            }
            cnt-=(int)del.size();
            if(backtrack(num)) check=true;
            cnt+=(int)del.size();
            for(int i:del) used[i]=true;
            if(check) break;
        }
        cc[x]=false;
        if(!check){
            //cout << "backtrack " << num << ' ' << cnt << ' ' << 0 << '\n';
            return false;
        }
    }
    //cout << "backtrack " << num << ' ' << cnt << ' ' << 1 << '\n';
    return true;
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> s[i];
    for(len=1;len<=7;len++){
        cnt=0;
        for(int i=0;i<26;i++) cc[i]=false;
        for(int i=1;i<=n;i++) cnt+=(used[i]=((int)s[i].length()==len));
        //cout << len << ' ' << cnt << '\n';
        if(cnt && backtrack(len)){
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;cin >> test;
    while(test--) solve();
}

详细

Test #1:

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

input:

3
4
BAC A B C
4
AC ACB C CA
6
ABC AC BAC CB CAB CA

output:

Yes
No
No

result:

ok 3 lines

Test #2:

score: 5
Accepted
time: 1ms
memory: 3620kb

input:

3
5
C CE CB ED EBC
6
BA CDE EB C EAC CD
5
A C BC D AC

output:

No
No
Yes

result:

ok 3 lines

Test #3:

score: 5
Accepted
time: 1ms
memory: 3620kb

input:

3
8
AG C GD B EA AFD D G
7
FG G E A GCB D CA
9
DE CAE E EAC AFG DCG GF D EB

output:

Yes
Yes
No

result:

ok 3 lines

Test #4:

score: 5
Accepted
time: 1ms
memory: 3764kb

input:

5
13
BF A F ADE AE EC EA CF CDF FE B AF CD
13
FDC AEF A FEB D B BA BAC ABE BFC F CE AFB
10
FEB BF CAD F EA AF DF FE BAF A
10
DEC D BC BFD B C FCA EF CE FE
13
C CA DAE D F FBD B FE AE AF A E AC

output:

Yes
Yes
No
Yes
Yes

result:

ok 5 lines

Test #5:

score: 5
Accepted
time: 3ms
memory: 3664kb

input:

4
49
FG GBCD EFAG GCF EG ACF FEA FCED CFD BCGA GACB CEG BAF FCB GBCF FD CBE DAF AC AB DBGA AGEC FC EBGA BA CB CG FDC CGA EGC AFD GEBA BCG BFAC DAC AD BCGD ADC EDAB ADBF AGC GD GDC ECD BCAF CFGD FCAG AEG FCG
49
FEDA FAC BAD BGEC EDA BCF ADC DGBE EABG AEDF BG GDCF BGC BAG AEF DGE ABEC EFD FAE AECB AGC...

output:

Yes
No
Yes
No

result:

ok 4 lines

Test #6:

score: 5
Accepted
time: 7ms
memory: 3616kb

input:

4
59
ECA CEBG BCF BEHG BA AEGH EDB CAH AHGF AHE GAFB GCEA FDGH DAGF EBAD BHG FHED HED GCFE ABGC BFEA BFA DEBG AEH ECD ACH CEFA HDA CFHD FHDB ACD HGA HFD CBG GBE CE AHG AHFE BFCH GHAD HF FHG BE AFH ADG HAC DAE AFGD HEFB BHCD HGAB EFA DGC GCA HBDF ACGB BAED CGD EHCA
58
EGBH DCHA BHC CDH CED CGDF FDHG ...

output:

No
Yes
No
No

result:

ok 4 lines

Test #7:

score: 5
Accepted
time: 71ms
memory: 3600kb

input:

4
88
DGCF DGFH EFGC BCAG EHD BCG CAH HBF BDH AHDC BFE CDFA ECDB GEA CAG GDA AHCF DCH DEG CDG FAB FBG ABFH BDCH CABD DCAB BGHA GFDE AHBD EGHB FHB GFB DE CEB ABD AHDG HFCD GBDE DBCF AB CBD EDH EAD GAB HBDA CGD CFAE GFAE ABCF BEC BGF ABG FECG FE DACB BADE HE GBE BEF CAED EHCD DB GDFE BCD HADC HGD CG HG...

output:

No
Yes
Yes
Yes

result:

ok 4 lines

Test #8:

score: 5
Accepted
time: 233ms
memory: 3616kb

input:

6
88
ADF EBA DCA HEB FGA CBD CEB BCG AHF FEBG HGFA HFE ADE DEA BHF AHG BGC EAF FAG DCHG AGF EGDC HGE GCA AEH HED FHD GH GAB BCF CGED ACHG FBHA CFHE CB DHA FADG DBHE AGE HGB FDHA FHEB FDG BGF HDBA DBH AHBF DCEB BHDG DBG HEF FHEA HC CGB FCGH HCB FGEB GFEC EGBH BCD HEFC CBG FBD DAGC EADF DAH FHG FBG BF...

output:

Yes
Yes
Yes
Yes
Yes
No

result:

ok 6 lines

Test #9:

score: 5
Accepted
time: 5ms
memory: 3676kb

input:

5
70
BE BAC CDA DCB BCD BECD BDC DAB BCA ABD CAE AEB BDAE AED CDB AE ACDE ECDB EB BEA ACB ECA ECB BC DB AEDB BD BEAD DC DEAC CAEB ADB AB DCE CBA CDEA EDB EAB DE AD EC DBEA BEC EAD D BCE CA ADC DCA CBE CAB ABE EBD EDA ECD EDC DBE EBCA EBC CED CDE DAC CDBA ED DABE ECDA ACD ACBD BA DAE
79
DAC BCE DCE A...

output:

Yes
No
Yes
Yes
Yes

result:

ok 5 lines

Test #10:

score: 5
Accepted
time: 8ms
memory: 3576kb

input:

5
90
DAF CED EAF FBA ED DCE CFB FBC CAD BDC EAC BDF ECF EAB BCE AFBC BD AFC BC BAF DAE DAFB BADF FEDC EDF DCA ECAD FDE ECAF BEC FBAD DFE CDA AFE BCEF ACF ACEF DABE EFDC DB EFBD DCF AEBF AB ABE ACD EBA EDC DCB AFCE FAD BCF ABC DFC AFCD BFEC CAB CF EBC BED FB DBEC FDBC DF CEF DBF DEF CFED CEFB EAD CDB...

output:

No
Yes
Yes
Yes
Yes

result:

ok 5 lines

Test #11:

score: 5
Accepted
time: 121ms
memory: 3588kb

input:

5
146
GDHC FAD BFHA CFEG GHC CEBHA FAEDC AFHDB EHBD HEBA BEAHG GC HCAF HDBCG HDCEA DBEA EHF GBF DFE DFEC HBADF GEFCA EHGD AFEH FDEH CFDE BEFGC GDB HBAF EGABF EBH GCE CBGF HEA FAC DEG FCA DBE BFHD HCG FGHC HGCA EAGF FDB BFCED DCE ECBD FCD FBGC DHE FEBG GBCE EDAH FHEG CEAFD CGE FA FDBG BEGDH FCDG HDGF...

output:

Yes
No
No
Yes
No

result:

ok 5 lines

Test #12:

score: 5
Accepted
time: 393ms
memory: 3628kb

input:

5
144
AGEBF GHBA AGBH BHFG DE EHAF BEHA CGHA CGDA CFEH CBAFD HABGD DBAHC CDF DAGB HEBF HCA HEAC AFGE HDB GDEA EBHC EGDH GEDB BAC DBFA BGD BCF FAC DGB FGCDA AFB BFCG EHD BDEG ECA DEAG CFE FGACE GEFA HDFG CGA BAFC FHED BFCE HEC FED HCBA CAEG AGEC DEB CDAG BDF DGCHE EABF HDC EFC GFEHD EADG AGHE HCFG CD...

output:

Yes
Yes
Yes
Yes
No

result:

ok 5 lines

Test #13:

score: 5
Accepted
time: 377ms
memory: 3564kb

input:

5
192
DEHB CA DCHA BDAC GEB CAGB BCEFD AHGEF DGAB ECBG HDE EDFH EFD HDBCG BAED CD EBC HC AGE ADHBC GBHE GCFE DAH BGCFH BCDGF GAC EBAGF BCFE ACDFE CBDEH AFD HGD DHAE EGDC FAHD EBF FEGAC HBEF FDAE DHB FDGA FDBEG EDB CHDGE GBHD EACBF ECH GEDF DCBE EADG GCEB EGH FGCA BDHGA GAD EFGB GADF DHCFA HBG DGC CH...

output:

Yes
Yes
Yes
No
Yes

result:

ok 5 lines

Test #14:

score: 5
Accepted
time: 255ms
memory: 3604kb

input:

5
195
GCE FH HGF ACEGH HGEC GDAB BCDE DEBCF AEBFH BHF HEAC HFDGA BADG HCAD CEBHF BDCF CDAB GDEB GECH EGBD ECDH CDHF HEBA HGED CBF FHBG FHDCA BAFD BHGA EGD DCBFG CBAEF ACD GHBEA DCBFA HBE AFBG DAFH GACB HCAE EBHF AFBDC BAHEG FGDEC HDCA GDB DGEB ADCB GHCFB GFBC FDCH AEHBC HGFB BC DFHC DBF FGED BGEH AC...

output:

Yes
No
Yes
Yes
Yes

result:

ok 5 lines

Test #15:

score: 5
Accepted
time: 12ms
memory: 3588kb

input:

5
148
CADB CE EDAC DAEC DEA DEC BAD EBC ECB ABDC ACBD EADCB BAC CABE CBE CBED ABED DEBA ACDB AEB CDBEA EDCB CDAE DEACB CBD CEDB EDBA ACE ACB CBA DBE BEA EDAB EDB DBEC BEAC AEBC BCA BDAC EADC BC DAC AEC ADBE BECD ECAD ABDE AEDC CBDE ADC DACB EBAC DCEB EC ABE CEBD DABE BDAE BDE ABD CBDAE CEB ABCDE ADC...

output:

Yes
Yes
Yes
Yes
No

result:

ok 5 lines

Test #16:

score: 5
Accepted
time: 145ms
memory: 3624kb

input:

5
194
DEFC BADF AEFC BDFE EBDC EAFB BECA EDC DAB FCEAD DBCF DACB EFCDB EBCF BAE DCF EBDA FBDA BDAF FC BC DABF ADFB BDE FAB ABF ACFD DAECB DA CE AEF CFEB EDBF FACD ADE FBCE FCE CDE CEB FDE BEA BFA BFDC DBE DFBC ECFA DBC DAEB AFBC BADE DFC DEB CAFB FADB BAEF FBDAE ABE DBA EBD EFBDA BEF FEBC AEBC EDCF ...

output:

Yes
Yes
Yes
Yes
No

result:

ok 5 lines

Test #17:

score: 5
Accepted
time: 236ms
memory: 3776kb

input:

5
246
CBAFH HAEDC HFBA FABC GEBF CHBE FEAHB HGDBEA DBHEG GEHBF EGFA DECF CEHG GEHFC BECGHF BACHG BHAE CBFEA FDAGH BAF CDGBA HGDAFE ADE BADHC GCHAFD GFEA BFGDE HECG EFDG DGHF FBCG CHBG FDBGA BDHEF DGEH GFB DHBG GDFHE FGEBC EAGCH HAFD BDHGA BEAC CGAFH GDCHB GBHE DAB BGDAH HDGF FADEB BFD CEBD ACFHD CAB...

output:

Yes
Yes
No
No
No

result:

ok 5 lines

Test #18:

score: 5
Accepted
time: 279ms
memory: 3624kb

input:

5
249
CBFGE DGFB DCFGH EBAHC DBFEG GCHDB BACED GBHD GAHDC CBFD HEADG HBFAG ADCH ABEFD BGEFAD FCGBA EABDC CAH EADCF ABCD EBDFHA ADBH HABDG CBF CDFA CBAF BEFGD DFGB AGFE GBED BFCDH GBHDE CEAB GCFBE GBE FHAG FDECB DFHACE HB GEFD GAB EHDBA HDFCG EBGHD BEHA CGED BFEHD CEAGD BDGFE CEGA FAEB CEAFB DCHFA CE...

output:

No
No
No
Yes
Yes

result:

ok 5 lines

Test #19:

score: 5
Accepted
time: 884ms
memory: 3792kb

input:

5
479
DEABG FBCGE HDC FDHCB CDHGA GHBA GDFBA GFBAH ACBDF EBAG BHDCA CDEHF ADHEC AHFD HBFA CHFB AEDHG AGBE DGCEF AGBED AFGED ADEF BEHA BED FBAEG HAD BDHA EDBCG EAGHF BFAED CBAF ECFH HDAF EBCDA GFBEA FCED HBDGE BEHC DCEGB HBGFAC AFBHE DFHCA GFBDA HDGF GBDF AGFH DGCA FDAHE HEA HCFED CBEGF CEGH HED CFAG...

output:

Yes
Yes
Yes
No
Yes

result:

ok 5 lines

Test #20:

score: 5
Accepted
time: 863ms
memory: 3796kb

input:

5
487
DAGCH GE GBFC HEFDAG BEADF CEBHAD BCEA HEGB ACBHG EDCFAG FBDC FDGC GACHBE EBHCG HFCA DBG DHAF EFBA ACEF ADBCEG BDHF CADG HAFGE CDHFB BHEG BAH HEFG DEBA HGFE EFCH FEBA HCBDAG CAGH GDHA DGAF HFGAD BGCAH ECAF HBCA GHFBD FABH HGBAC EDCA CFGHB AEFC HBGFA FHE FACDHE GEDFB GHAD DECHB HBFG CFDG GBFEH ...

output:

Yes
No
Yes
Yes
Yes

result:

ok 5 lines