QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#469190#7236. Set intersectionpropaneAC ✓679ms152856kbC++201.3kb2024-07-09 15:47:162024-07-09 15:47:17

Judging History

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

  • [2024-07-09 15:47:17]
  • 评测
  • 测评结果:AC
  • 用时:679ms
  • 内存:152856kb
  • [2024-07-09 15:47:16]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<random>
#include<bitset>
using namespace std;
using LL = long long;

template<int len = 1>
void solve(int n){
    if (2 * n > len){
        solve<min(2 * len, 12000)>(n);
        return;
    }
    vector<bitset<len> > bs(n);
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        int cur = 0;
        for(auto c : s){
            int x = c - 33;
            for(int j = 0; j < 6; j++){
                if (x >> j & 1){
                    bs[i].set(cur + j);
                }
            }
            cur += 6;
        }
    }
    vector<pair<int, int> > p;
    p.reserve(n * (n - 1) / 2);
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            p.push_back({i, j});
        }
    }
    shuffle(p.begin(), p.end(), mt19937_64(1479142375923));
    n /= 2;
    for(auto [l, r] : p){
        if ((bs[l] & bs[r]).count() >= n){
            cout << l + 1 << ' ' << r + 1 << '\n';
            return;
        }
    }
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    solve(n);

}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3504kb

input:

4
7"
*$
D#
M"
;"

output:

2 3

result:

ok OK (n = 3, i = 2, j = 3, intersection = 2)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10
EVK#
IH=#
676"
R7,#
74S"
6V2#
O3J#
S-7$
NU5"
C[$$
3N.#

output:

5 8

result:

ok OK (n = 9, i = 5, j = 8, intersection = 5)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

10
*L:#
U/;"
L6M!
7SG#
RW+"
>C4"
&8G#
"^5$
,RK#
*8S#
863"

output:

5 8

result:

ok OK (n = 9, i = 5, j = 8, intersection = 5)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

10
O7+#
=IZ#
J0A$
2LV!
>-8!
2:,$
[28!
W5M#
JK4"
F3]"
'8/#

output:

4 7

result:

ok OK (n = 9, i = 4, j = 7, intersection = 5)

Test #5:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

100
YW;V6F:$&&SES7O3&<6H+UVS.2\SN.45Z!
.D!OF66*HVKEQVO7,#B3F.8,>:\:U?Y;4#
]/NM4<FNEF5+=%XKRE6JBSUWG%6GM>ZGG#
:76W;L9I45N7<N&JYWI>JA4FW[2OUES37#
TK>4M.FTFS)GM6G1;U?8F'>;L#K>3#S;N$
K-FSJW)WA"N+JX'.FG-VV48M&61>KKNN\#
F>FO4NP4$54)I566[;,UK/8XCS7S+U/D'"
O26G',7W.UVW4*7%FV7MK>O5588X1FLS1!
6R=<-<26'J&26>.K...

output:

11 15

result:

ok OK (n = 99, i = 11, j = 15, intersection = 55)

Test #6:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

100
.4DOBV94FKFMQI*ZM6<8-WOD=XIV[C4&3!
KN><K5=E0<&.677+S*=636:,WK-37H+6H$
XYM)D2NOI[+<BAKE:ZBHN[3K6UK+U6N[7"
8\1F9/+MCM/N;3E;LOI+Z-L968$<JK]3\#
5ZOG':+962KG5BV1,48_;25V[3=?7\G;<#
:+5@G#F*;5W1PYNPW=T3,4-EK)E6P&NN,$
O-,2V5DO<PRF+=$4,HHJ&BNEBO3:&3TJ8"
KE;+6M<VO4[33Z)VU'VKKKXI5&>D:JS;D"
D&<W36O3U?%VWE5H...

output:

45 61

result:

ok OK (n = 99, i = 45, j = 61, intersection = 52)

Test #7:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

100
VI516%@-W;JJZ><ENRWG=L2FI;>&L;.$D#
>+DI=WWYJJTUS%V/N7K,4-*V35#NDGMKL$
J+ELL4;6<NE6"6F.FG6@F,N;2/JFO)83>!
);5WHYU;S:\7NKC=484ND@7+NCK6)2N%G"
LI+AYKK<[=XBN+E6H3LK6V98-KO3+2TGV#
HAN\*L+JE87%8L-E+N&0(YVNQ'VGNIW-]!
^6T+<\Y5S.:*KKJJ7RJSTRFMQ-I^-;#NE#
44I+>M*NOV3+3G+*ZO:5P3%08>N6['Y3L"
1?6G<FYIZE6SV1>,...

output:

15 64

result:

ok OK (n = 99, i = 15, j = 64, intersection = 50)

Test #8:

score: 0
Accepted
time: 13ms
memory: 7348kb

input:

1000
MK;0=:K8JI5KU9IQS]FWO=LKFF7R9<U-6S5KF3DQB+ZG+[;9LZ)6X[2';:7(.,7)\/L.*/,68X2=,V5ZM;,X69S3LK3K/$FNUZ[5XJ;7K9X7LGVVCKZ&2=5C,7.6*F,JO5?KK)48+:.E,W;-:VLN&F/O).GF#&NF2K6.V]D=7J784G+)SZ+EMB;VF.[YU6>S%<*K5>&NKI3D56>E+MG65O/\+LJL'$\S+:+.F1\I"6SEW$8G<NRW>6K>K4[3MN?H:JW'JF8;F/RMRC1VS'53OT6N\N/NQW6LNU6)O3K...

output:

522 852

result:

ok OK (n = 999, i = 522, j = 852, intersection = 515)

Test #9:

score: 0
Accepted
time: 6ms
memory: 7332kb

input:

1000
N56-<'I/[ENG\1[EG.C85<V[:&^C7"755M7<UN.3;;36S[*6.\!4##JK*5.KNM9P$3FW['NG*3X9VSEG=-K[=#;.JUM6F<I55<6KO5TFG+VG7\:NFE&F&;&..666F.)X:\5T<<NNO<F+3YWK)7V9C6%J[=OMW"7$W&K25$M'L\K68JW9\CNU6L6W;J3.NM^IRM6:KOG'VWUK=,DN*>,6<W;68NK;S?GEL26VLKL6^VF#G:$3REQ5RGV%?D?1XG2;5VWJ=,LS3TI#<2XO7NN*MRN0QA*ERV[GA,0.%K<...

output:

493 881

result:

ok OK (n = 999, i = 493, j = 881, intersection = 504)

Test #10:

score: 0
Accepted
time: 10ms
memory: 7288kb

input:

1000
^::8KA+G3<14K;*5:MN=QH+-2^2"N3C)BG'X7BS5&M(V9<IG;6N<1L7_5:Z'C>$[VK"CYI=K+[;)W_Z5WL6*6N#NV5\AG&.=62YSS)C/P\M6+LW!T>4;PE-Q5OE5K<$+FX;F9;82R=+J5WKN^9ZIUBM#L7,>3&4H'X=3:[email protected]+F;%V<LQOCN3-EM\;=*%\'+2TKKXGW385SGLN7NIKI5L4GG\;R5V,6Z7,6,PXWSQM5N:D*/@KVK\GDF>D&4;J+<:LW6VSV,W#ZKAK+H=VO.LWQ<OI:DI4VO1VF<E...

output:

522 852

result:

ok OK (n = 999, i = 522, j = 852, intersection = 513)

Test #11:

score: 0
Accepted
time: 148ms
memory: 41404kb

input:

3000
(_CK[GW7'HZLKK3<X+W+8>,TSK,NU9.6LK*=)F5>7><R5C4!CSFLLYS;V"17FMJT+\J&<FG>',X61%L>X'\M?,C7$MWS+:D6L*-5\74N'LU+7K.D5<F6\7H6FJW1N;;5MN6&$C68U98-2GE=JE526=3^[:RQ^;5AG*FVU3<;<?LV]SGW7^KKW'05.>4J77IT7&J"\M%,366737HG4*F+PKIM9_WSM6[^KW&4FBQKI,6#$33>HN6G5.NK+(>K;8N5Y3QOD6QUM9NGKMNO[M>H%!<DC;#<`GKZ+L73LE$...

output:

1559 2497

result:

ok OK (n = 2999, i = 1559, j = 2497, intersection = 1503)

Test #12:

score: 0
Accepted
time: 162ms
memory: 41432kb

input:

3000
^#;E;3V.J+G]-JMI<.VK6&3764FMQ.#>*OW7NCS"<L;J2L/+T5\G*C,&;#(V#4&YG3PJQ7SM7G&"<5L7&<>;TCM+:9LN[KVR76-LM#OGM7U46WL;C.K3N8GLEN^OU36[5<FO>XNH:;EV<;#,>X?4>RUUS,PM9X5'^#SVCR+F0]A&C&L5HY3X+3NV7-FL.F;U3LM&,USKGOTK7K<-K^MFWO;E<ZV;B%L5IM*TX)JO,V$*FAJKDL.=+,NJ>;KU[M6*V6VRNSJJ"5656"3LC[5V6BW7+F!,LCB+-&<<MFW...

output:

1817 1981

result:

ok OK (n = 2999, i = 1817, j = 1981, intersection = 1531)

Test #13:

score: 0
Accepted
time: 154ms
memory: 41420kb

input:

3000
$V*M#(K6.V7[/OE<N7VQ[54$1\)6.\F0&-.2%E>\;-;YL,7Z-&RG;$;<3%[E;7W6+6O\6;V;6<J5C>P8UO.<7HVTI;W5RO6-XC&H>NI]O&FKKM>B4[EFNIW!L6/.J;B[3,6JV5<.=6NGR*:NLM9W,]DO->$\MJ2LS)N;S7<4E;LK2N3=@LWUI1U]V1L;7P#3<8WVSCE$TV676U)MWER8>M#J922$5J;'IAK3FL6KK7KW-OCVEF*DY$0NFN'>7H3LV>J,6';]@",L&N46K4J*SR4<2E6L'$M1XI-FGV;...

output:

1559 2497

result:

ok OK (n = 2999, i = 1559, j = 2497, intersection = 1536)

Test #14:

score: 0
Accepted
time: 679ms
memory: 152716kb

input:

6000
67X"=!W?*M+PMG+6-8B>$&V)94:61\TOKGGB/\W[MONK+::ZK3NJKCKE&7FV:..4'.D2YIU5LCF1DB7;6SK2[7H*4+<NLFJS&<X;>5X#&70[5HK<NN:<&3LC+J56GK;;9.LO.T66:DX%XV;5/+<3L#J8ME6L+6J8ZGTV9<6J%:JK5#P7N&>!:+W'4GMH>4UKJT*&F98SG5M5;:6)\SH5S;36>MX9KWFP&&T;#LEIK\.^T47AJIMES)*J.ULC3<NU;T_IEJ6<M<LJJM7K6NN;KXW7W7.+KW66K*X7V3'...

output:

1535 3498

result:

ok OK (n = 5999, i = 1535, j = 3498, intersection = 3014)

Test #15:

score: 0
Accepted
time: 647ms
memory: 152732kb

input:

6000
3+XSVMX[V8U7<4T7648<<+VFF7WE+NF5O<X5QV+(Y3RE.N/V;$LGF6G:^K2;7QLI7*(IV+B1<6N,=>26!H5"3>JO3D4KWWR9&K8G6361-<VF#N52;BLK+V3<L.>J-KK'N5]WJUWK9,T5F'FE6P<357?[UZLAH"TC2+<^NY\'NMGM5KKK[3&UU58$Y%P;LN=&L)MEF3MV*L,KAWI6V+BWU,N?[7.LCM)^3_Q<:C;4:FN;V5[NJLJ'*7;6HQRM;F3S=WF;<9KWVU72;S\NX2JE+Z>9V5\WOOMW'3.<,JG...

output:

1535 3498

result:

ok OK (n = 5999, i = 1535, j = 3498, intersection = 3016)

Test #16:

score: 0
Accepted
time: 628ms
memory: 152856kb

input:

6000
3=J67;K-U/TKNU5KNWKCO8+/%"Z#6P:6D.<W?QOOVU;&<6V=^W75-Z546GCM*LKR"?CG1&.E?OJGGKU'SEN+S3+8LM\7MJ%3F?5LV27JB=8.N67S6<1*61=3<KOM*%JY9)8\1VMT?^5GYM3HI^[3M5K[JTG.7)M%>I+#"':V;$L6FN7N$8I''UNJB>KU.B1K?21MQ7;.6X5Y;N!+E7)2\;7V5C1\7V<6<>P6OV8Z;L6B56*,IE27Z-E:.8^JT?VJ4=WUKUW^5L.JA;L1BDT7S3E9VC+,8ENV:8;\O32...

output:

298 3853

result:

ok OK (n = 5999, i = 298, j = 3853, intersection = 3018)