QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#309387#7531. Hacking the Project8BQube#RE 117ms210336kbC++202.6kb2024-01-20 17:00:092024-01-20 17:00:10

Judging History

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

  • [2024-01-20 17:00:10]
  • 评测
  • 测评结果:RE
  • 用时:117ms
  • 内存:210336kb
  • [2024-01-20 17:00:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

int dp[27][1001][1001];
int pi[27][1001][1001];
bool valid[27][1001][1001];

int get_dp(int rounds, int l, int n) {
    // dp: cost
    if (valid[rounds][l][n]) return dp[rounds][l][n];
    if (rounds <= 0 || l >= n) return 0;


    dp[rounds][l][n] = 1e9;
    for (int i = l + 1; i <= n; ++i) {
        int tmp = 0;

        // guess i

        // judge: < i; exactly l;
        tmp = max(tmp, i + get_dp(rounds - 1, 0, n - l));
        // judge: >= i;
        tmp = max(tmp, i + get_dp(rounds, i, n));

        dp[rounds][l][n] = min(dp[rounds][l][n], tmp);
    }

    valid[rounds][l][n] = true;
    return dp[rounds][l][n];
}

constexpr int kInf = 1'000'000'000;
vector<int> crit(int l, int n) {
    vector<int> v;
    for (int i = -5; i <= 5; i++)
        v.push_back((1 + l * 2) + i);
    for (int &x : v) {
        x = max(x, l + 1);
        x = min(x, n);
    }
    return v;
}

void solve() {
    int _n;
    cin >> _n;
    set<string> st; 
    for (int r = 26; r >= 1; r--) {
        int l = 0, n = _n - SZ(st);
        do {
            int i = pi[r][n][l]; 
            cout << "query " << (char)('a' + (r - 1)) << " " << i << endl;
            int k;
            cin >> k;
            for (int j = 0; j < k; j++) {
                string s;
                cin >> s;
                st.insert(s);
            }
            if (k < i)
                break;
            else
                l = k;
        } while (l < n);
    }
    assert(SZ(st) == _n);
    cout << "answer";
    for (auto s : st)
        cout << " " << s;
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (int r = 1; r <= 26; ++r) {
        for (int n = 0; n <= 1000; ++n) {
            dp[r][n][n] = 0;
            for (int l = n - 1; l >= 0; --l) {
                dp[r][n][l] = kInf;
                for (int i = min(n, max(l + 1, (1 + l * 2) - 5)); i <= min(n, (1 + l * 2) + 5); i++) {
                // for (int i : crit(l, n)) {
                // for (int i = l + 1; i <= n; ++i) {
                    int x = i + max(dp[r - 1][n - l][0], dp[r][n][i]);
                    if (x < dp[r][n][l])
                        dp[r][n][l] = x, pi[r][n][l] = i;
                }
            }
        }
    }
    int T;
    cin >> T;
    while (T--)
        solve();
}

详细

Test #1:

score: 100
Accepted
time: 63ms
memory: 209476kb

input:

1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 cxyxy
2 cxyxy czzzz
0
2 aaa aba

output:

query z 1
query y 1
query x 1
query w 1
query v 1
query u 1
query t 1
query s 1
query r 1
query q 1
query p 1
query o 1
query n 1
query m 1
query l 1
query k 1
query j 1
query i 1
query h 1
query g 1
query f 1
query e 1
query d 1
query c 1
query c 3
query b 1
query a 2
answer aaa aba cxyxy czzzz

result:

ok Ok in 30 k

Test #2:

score: 0
Accepted
time: 108ms
memory: 210224kb

input:

5
1000
3 z zbve zcepigpbz
11 z zbve zcepigpbz zdrqonowwv zejf zfiayfvo zgtvmowlbe zhbpv zi zikg zjkteof
28 z zbve zcepigpbz zdrqonowwv zejf zfiayfvo zgtvmowlbe zhbpv zi zikg zjkteof zkpttslil zmaecxfpk zmefwcrvy zmnoozl znjbexal zoampo zoptul zosj zotoyqryuy zpvwoc zqsjhrllov zqx zsfgmcou zsnfhrafbq...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 27
query y 60
query x 3
query x 10
query x 26
query x 58
query w 2
query w 9
query w 24
query w 54
query v 2
query v 9
query v 24
query v 53
query u 2
query u 8
query u 22
query u 50
query t 1
query t 8
query t 21
query t 47
que...

result:

ok Ok in 2538 k

Test #3:

score: 0
Accepted
time: 97ms
memory: 208256kb

input:

5
1000
3 zauu zbczeg zbnduo
11 zauu zbczeg zbnduo zcvdyfwuh zcymx zcyqpxanft zfexxafmka zfzi zhbpv zhdpmvnurn zi
28 zauu zbczeg zbnduo zcvdyfwuh zcymx zcyqpxanft zfexxafmka zfzi zhbpv zhdpmvnurn zi ziqurwrbr zivghxaigw zj zlkgyv zmbm zngj znpxzsfg zotwfle zpghkv zpoxtqdfpj zqmeeyehje zqrgjkwp zrnwwv...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 12
query y 29
query y 64
query x 3
query x 10
query x 26
query x 57
query w 2
query w 10
query w 25
query w 55
query v 2
query v 9
query v 24
query v 53
query u 2
query u 8
query u 22
query u 50
query t 2
query t 8
query t 21
query t 48
qu...

result:

ok Ok in 2560 k

Test #4:

score: 0
Accepted
time: 78ms
memory: 209048kb

input:

5
1000
3 zapun zbvxzfc zbwxmpobm
11 zapun zbvxzfc zbwxmpobm zcfabbkoxy zcu zeqqzrl zfzgt zgjszebt zhpxneofh zitqgqiphv zjkteof
28 zapun zbvxzfc zbwxmpobm zcfabbkoxy zcu zeqqzrl zfzgt zgjszebt zhpxneofh zitqgqiphv zjkteof zjmmyfm zjq zjqaw zkpttslild zlced zlkgyv zlz znjojvl znkmzukai znmnnxw znpxzsf...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 27
query y 60
query x 3
query x 10
query x 26
query x 58
query w 3
query w 10
query w 25
query w 56
query v 2
query v 9
query v 23
query v 52
query u 2
query u 8
query u 22
query u 49
query t 2
query t 8
query t 21
query t 47
qu...

result:

ok Ok in 2626 k

Test #5:

score: 0
Accepted
time: 96ms
memory: 210180kb

input:

5
1000
3 z za zafa
11 z za zafa zagrfn zbcze zeciu zgruhhc zhu zijpjku zjkteof zjqtlkiqy
28 z za zafa zagrfn zbcze zeciu zgruhhc zhu zijpjku zjkteof zjqtlkiqy zkp zldr zlkeamdxa zlxwfrsl zlztks zmojnhig zmrys znjbex znmnnxwra znpxzsf zoampo zogrltul zqmgovmvg zqxy ztvcgvz zulhk zv
38 z za zafa zagrf...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 27
query y 60
query x 3
query x 10
query x 26
query x 57
query w 2
query w 9
query w 24
query w 54
query v 2
query v 9
query v 23
query v 52
query u 2
query u 8
query u 22
query u 49
query t 1
query t 7
query t 20
query t 46
que...

result:

ok Ok in 2572 k

Test #6:

score: 0
Accepted
time: 91ms
memory: 208988kb

input:

5
1000
3 zcl zdwtok zeualg
11 zcl zdwtok zeualg zfp zgd zgtvmo zhysadroq zk zkhz zmaecxf znd
28 zcl zdwtok zeualg zfp zgd zgtvmo zhysadroq zk zkhz zmaecxf znd zndtlu zo zoqo zpv zpwomz zqaqgvfdx zqmeeyeh zqmg zrny zt zuqdebij zvrk zw zwylizmr zxqmlswv zyooh zzbczeg
29 zcl zdwtok zeualg zfp zgd zgtvm...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 27
query y 60
query x 2
query x 10
query x 26
query x 58
query w 2
query w 9
query w 24
query w 54
query v 2
query v 9
query v 24
query v 54
query u 2
query u 8
query u 22
query u 50
query t 2
query t 8
query t 22
query t 49
que...

result:

ok Ok in 2517 k

Test #7:

score: 0
Accepted
time: 110ms
memory: 209272kb

input:

5
1000
3 zbnduoa zbrskza zddwxttf
11 zbnduoa zbrskza zddwxttf zdrq zebtaqq zeciucl zfcshc zfiay zggt zhdpmvnu zheqxiwhf
28 zbnduoa zbrskza zddwxttf zdrq zebtaqq zeciucl zfcshc zfiay zggt zhdpmvnu zheqxiwhf zhg zijdwt zinro zjgl zjq zkbhzkh zlcedw zmae znj znpxz znzvrkmj zoamp zobd zotwfl zpghkvjco z...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 27
query y 60
query x 2
query x 10
query x 26
query x 58
query w 3
query w 10
query w 25
query w 56
query v 2
query v 9
query v 24
query v 54
query u 2
query u 9
query u 23
query t 2
query t 8
query t 22
query t 50
query s 1
que...

result:

ok Ok in 2605 k

Test #8:

score: 0
Accepted
time: 96ms
memory: 208900kb

input:

5
1000
3 z zbnx zcvd
11 z zbnx zcvd zdr zejfdo zeual zf zfcq zgec zggtllud zgruhhc
28 z zbnx zcvd zdr zejfdo zeual zf zfcq zgec zggtllud zgruhhc zgtvm zisucll zjq zkpttsli zlkg zmrys znoa zoootorz zopt zpuuve zq zqj zr zsrpgvdu ztti zuovqew zv
40 z zbnx zcvd zdr zejfdo zeual zf zfcq zgec zggtllud zg...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 27
query y 60
query x 3
query x 10
query x 26
query x 57
query w 2
query w 9
query w 24
query w 54
query v 2
query v 9
query v 23
query v 52
query u 2
query u 8
query u 22
query u 50
query t 1
query t 8
query t 21
query t 48
que...

result:

ok Ok in 2604 k

Test #9:

score: 0
Accepted
time: 98ms
memory: 209756kb

input:

5
1000
3 zaf zbrkgvy zbv
11 zaf zbrkgvy zbv zdb zdltth zdr zebtaq zejfdopd zf zhpxn zhv
28 zaf zbrkgvy zbv zdb zdltth zdr zebtaq zejfdopd zf zhpxn zhv zijp zj zjkte zldbbeem zma znkmzuk znp zo zoootor zoq zpghkvjc zrrdd zsf zul zurjpoah zvlkeea zvr
32 zaf zbrkgvy zbv zdb zdltth zdr zebtaq zejfdopd z...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 27
query y 60
query x 3
query x 10
query x 26
query x 58
query w 3
query w 10
query w 25
query w 56
query v 2
query v 9
query v 24
query v 54
query u 2
query u 9
query u 23
query u 52
query t 2
query t 9
query t 24
query t 54
qu...

result:

ok Ok in 2559 k

Test #10:

score: 0
Accepted
time: 91ms
memory: 208908kb

input:

5
1000
3 zagrf zbcvoy zbw
11 zagrf zbcvoy zbw zcaqjd zcv zebtaqq zeghm zejf zeqf zfhkplwu zgec
28 zagrf zbcvoy zbw zcaqjd zcv zebtaqq zeghm zejf zeqf zfhkplwu zgec zguzzyq zhb zhuer zhvcdoo zjd zjk zjmm zkptt zld zldbb zlwc zmx zmyfruw zoeo zoprfeec zosjlr zpl
49 zagrf zbcvoy zbw zcaqjd zcv zebtaqq ...

output:

query z 3
query z 11
query z 28
query z 62
query y 3
query y 11
query y 28
query y 62
query x 3
query x 10
query x 26
query x 57
query w 2
query w 9
query w 24
query w 54
query v 2
query v 9
query v 23
query v 52
query u 2
query u 8
query u 22
query u 49
query t 2
query t 8
query t 21
query t 48
que...

result:

ok Ok in 2679 k

Test #11:

score: 0
Accepted
time: 77ms
memory: 208560kb

input:

5
1000
3 zaaagkfan zaaakob zaafd
11 zaaagkfan zaaakob zaafd zabeang zaujeeeky zbcqa zbmdbpvdoc zbojpsemfd zbsrg zccgacbke zccpimif
28 zaaagkfan zaaakob zaafd zabeang zaujeeeky zbcqa zbmdbpvdoc zbojpsemfd zbsrg zccgacbke zccpimif zcefd zcflhmb zchwbo zcpbtf zcuvii zdfczofae zdgjcp zdjbze zdszcgrufz z...

output:

query z 3
query z 11
query z 28
query z 62
query z 130
query y 3
query y 10
query x 3
query x 10
query x 26
query w 3
query w 10
query v 3
query u 2
query u 10
query u 26
query t 2
query t 10
query t 25
query s 2
query s 10
query s 25
query r 2
query r 9
query r 24
query q 2
query q 9
query q 24
que...

result:

ok Ok in 2672 k

Test #12:

score: 0
Accepted
time: 115ms
memory: 208788kb

input:

5
1000
3 zabeang zabrddec zaefzclal
11 zabeang zabrddec zaefzclal zagchekkbm zagzdkclsd zaujeeeky zazbezhla zaznflh zbaegmh zbbocfb zbfdlzk
28 zabeang zabrddec zaefzclal zagchekkbm zagzdkclsd zaujeeeky zazbezhla zaznflh zbaegmh zbbocfb zbfdlzk zbojpsem zbpjcspikg zbrefaaxf zbsrgbdde zccwehbz zcjftid...

output:

query z 3
query z 11
query z 28
query z 62
query z 130
query y 3
query y 10
query x 2
query x 10
query x 26
query w 2
query w 10
query v 2
query v 10
query u 2
query u 10
query u 25
query t 2
query t 9
query t 24
query s 2
query s 9
query s 24
query r 2
query r 9
query r 23
query q 2
query q 9
query...

result:

ok Ok in 2567 k

Test #13:

score: 0
Accepted
time: 116ms
memory: 209324kb

input:

5
1000
3 zabbnemecd zadjfg zakdzd
11 zabbnemecd zadjfg zakdzd zbebcb zbojhddsad zcaehdc zcbag zcczqzcch zcjftd zcoacfzi zdeaa
24 zabbnemecd zadjfg zakdzd zbebcb zbojhddsad zcaehdc zcbag zcczqzcch zcjftd zcoacfzi zdeaa zekaqjdl zfccdapbc zgaajne zhgibbsb zicwqce zikebdaf zkajl zkcakfbe zldeadh znbbb ...

output:

query z 3
query z 11
query z 28
query y 3
query x 3
query w 3
query w 11
query v 3
query v 11
query u 3
query u 11
query t 3
query t 12
query s 3
query s 11
query r 3
query r 11
query r 28
query q 2
query q 10
query q 26
query p 2
query p 10
query o 2
query o 10
query o 26
query n 2
query n 10
query...

result:

ok Ok in 2607 k

Test #14:

score: 0
Accepted
time: 95ms
memory: 209592kb

input:

5
1000
3 zaaaajbmb zacjijj zaemhcbd
11 zaaaajbmb zacjijj zaemhcbd zakdzdac zamahncu zanbkgf zbajeccmb zbbeabiif zbdalgvea zbebcbld zbggcaml
25 zaaaajbmb zacjijj zaemhcbd zakdzdac zamahncu zanbkgf zbajeccmb zbbeabiif zbdalgvea zbebcbld zbggcaml zbidebcb zcajkgr zcbagabza zcjftded zddaahzcr zekaqjdl z...

output:

query z 3
query z 11
query z 28
query y 3
query y 11
query x 3
query x 11
query w 3
query v 3
query v 11
query u 3
query u 12
query t 3
query t 12
query s 3
query s 11
query r 3
query r 11
query r 28
query q 2
query q 10
query q 26
query p 2
query p 10
query p 26
query o 2
query o 10
query o 25
quer...

result:

ok Ok in 2473 k

Test #15:

score: 0
Accepted
time: 93ms
memory: 209220kb

input:

5
1000
2 zcefd zgadka
0
0
1 wfeaa
0
1 uicicchs
3 taadaaab taeal tafefiika
5 taadaaab taeal tafefiika tamfkb tbqdnbjb
3 sbafahibd shblf sickcab
3 sbafahibd shblf sickcab
3 rccaadeda rdfaeec rdgbbbdagb
10 rccaadeda rdfaeec rdgbbbdagb rebghce rfaelehg rhehagua rjbea rkdicah rpgbfc rzabchd
3 qcabxlcbsa ...

output:

query z 3
query y 3
query x 3
query w 3
query v 3
query u 3
query t 3
query t 11
query s 3
query s 11
query r 3
query r 11
query q 3
query q 11
query p 3
query p 11
query o 3
query o 11
query o 28
query n 3
query n 11
query m 3
query m 11
query m 28
query l 2
query l 10
query l 26
query k 2
query k ...

result:

ok Ok in 2485 k

Test #16:

score: 0
Accepted
time: 78ms
memory: 208380kb

input:

5
1000
2 zdaebaab zebbcgdeea
1 ycaavaeeab
0
2 wadbffc wlcbsace
3 vbesacjaa vcfebcf vfebcbb
3 vbesacjaa vcfebcf vfebcbb
2 ufajeccbh uicicchsbe
3 tcibfaid tcwszab teafdaemie
3 tcibfaid tcwszab teafdaemie
2 sajeecbbaf sbigafc
3 rbbbaedbg rdgbbbdagb rjdaeaai
3 rbbbaedbg rdgbbbdagb rjdaeaai
3 qaacbtcdga ...

output:

query z 3
query y 3
query x 3
query w 3
query v 3
query v 11
query u 3
query t 3
query t 11
query s 3
query r 3
query r 11
query q 3
query q 11
query p 3
query p 11
query p 28
query o 3
query o 11
query o 27
query n 3
query n 11
query m 3
query m 11
query m 27
query l 3
query l 11
query l 27
query k...

result:

ok Ok in 2448 k

Test #17:

score: 0
Accepted
time: 92ms
memory: 208424kb

input:

5
1000
0
0
0
0
1 vdcdacaad
1 ubcai
1 taadaaab
2 sbcmcdcec sbhbb
3 racbbhaif rbcacbhfcg rfaag
4 racbbhaif rbcacbhfcg rfaag rfacgab
3 qcgdaeea qiablaafab qjceab
3 qcgdaeea qiablaafab qjceab
1 pnaeb
2 obbabdae odfhaeabdj
3 naeebbeccc ncbcadecaa nceambab
7 naeebbeccc ncbcadecaa nceambab nehbcd nghhabe n...

output:

query z 3
query y 3
query x 3
query w 3
query v 3
query u 3
query t 3
query s 3
query r 3
query r 11
query q 3
query q 11
query p 3
query o 3
query n 3
query n 11
query m 3
query m 11
query m 28
query l 3
query l 11
query l 28
query k 3
query k 11
query j 3
query j 11
query j 28
query i 2
query i 10...

result:

ok Ok in 2446 k

Test #18:

score: 0
Accepted
time: 106ms
memory: 210336kb

input:

5
1000
0
0
0
0
0
2 ucfebcfd ulcgmecjba
0
1 sdabacc
1 rdaqiabla
1 qdgfccaafb
2 pabbdbc pgabdcfe
3 oaeebbec oahabcaf obbabdae
8 oaeebbec oahabcaf obbabdae obdccaf obejbhbdc odaagsdc okiqkbbb onaebaab
3 nacblad ncfcaibe ndahbad
4 nacblad ncfcaibe ndahbad nebbeadfeg
3 maabcacgc maghcaja mbabbakaa
9 maab...

output:

query z 3
query y 3
query x 3
query w 3
query v 3
query u 3
query t 3
query s 3
query r 3
query q 3
query p 3
query o 3
query o 11
query n 3
query n 11
query m 3
query m 11
query l 3
query l 11
query l 28
query k 3
query k 11
query k 27
query j 3
query j 11
query j 27
query i 2
query i 10
query i 26...

result:

ok Ok in 2560 k

Test #19:

score: 0
Accepted
time: 117ms
memory: 209608kb

input:

5
1000
0
0
0
0
0
0
0
0
3 rcbedaead rfacdab rhfcdcbbb
3 rcbedaead rfacdab rhfcdcbbb
2 qddaa qjdbaah
1 pabca
0
2 nebaae nfcia
3 macaae mcbdbad mkahc
4 macaae mcbdbad mkahc mlbccf
3 labjeca lacad lacdb
7 labjeca lacad lacdb laeaaabgc ldammbcaaa leaaaaa lecdaa
3 kaabbdc kaaiccaec kadaafefc
10 kaabbdc ka...

output:

query z 3
query y 3
query x 3
query w 3
query v 3
query u 3
query t 3
query s 3
query r 3
query r 11
query q 3
query p 3
query o 3
query n 3
query m 3
query m 11
query l 3
query l 11
query k 3
query k 11
query j 3
query j 11
query j 28
query i 3
query i 11
query i 27
query h 3
query h 11
query h 27
...

result:

ok Ok in 2497 k

Test #20:

score: 0
Accepted
time: 87ms
memory: 209404kb

input:

5
1000
0
0
0
1 wbafabbabj
0
0
0
0
2 rcbedae rdcabjcba
3 qaacbjjbad qbcbdba qddaaeccf
4 qaacbjjbad qbcbdba qddaaeccf qhebcadae
1 pbiaaba
1 ogafahaa
3 naggaba nbabmabd ndcdajda
3 naggaba nbabmabd ndcdajda
2 mbabbakaa meaaaead
3 lacadba lahaeaaed lbbdcada
10 lacadba lahaeaaed lbbdcada lcbjcbaa lccffbad...

output:

query z 3
query y 3
query x 3
query w 3
query v 3
query u 3
query t 3
query s 3
query r 3
query q 3
query q 11
query p 3
query o 3
query n 3
query n 11
query m 3
query l 3
query l 11
query k 3
query k 11
query j 3
query j 11
query j 28
query i 3
query i 11
query i 27
query h 3
query h 11
query h 27
...

result:

ok Ok in 2478 k

Test #21:

score: -100
Runtime Error

input:

1
1000
0
0
0
0
3 vaaairmyxt vaaofrhqxr vacgbadpnx
11 vaaairmyxt vaaofrhqxr vacgbadpnx vacvztknmn vadyjiuebd vaeepwltck vaiirttzps vajfgasmgp vajfljeggd valvfqcyfk vamnvvfoso
28 vaaairmyxt vaaofrhqxr vacgbadpnx vacvztknmn vadyjiuebd vaeepwltck vaiirttzps vajfgasmgp vajfljeggd valvfqcyfk vamnvvfoso va...

output:

query z 3
query y 3
query x 3
query w 3
query v 3
query v 11
query v 28
query v 62
query v 130
query v 266
query v 528
query u 3
query t 3
query s 3
query r 3
query q 3
query p 3
query o 3
query n 3
query m 3
query m 12
query m 30
query m 66
query m 138
query m 274
query l 4
query k 4
query j 5
quer...

result: