QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#309387 | #7531. Hacking the Project | 8BQube# | RE | 117ms | 210336kb | C++20 | 2.6kb | 2024-01-20 17:00:09 | 2024-01-20 17:00:10 |
Judging History
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...