QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#98969 | #4237. Word Ladder | Zomara# | AC ✓ | 105ms | 3932kb | C++20 | 1.8kb | 2023-04-21 03:52:18 | 2023-04-21 03:52:19 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;
template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
set<string> st;
bool bad(string &s, string &prv)
{
string t = s;
for(int i = 0; i < s.length(); i++)
{
for(char c = 'a'; c <= 'z'; c++)
{
t[i] = c;
if(t == prv)
continue;
if(st.count(t))
return true;
}
t[i] = s[i];
}
return false;
}
void doWork()
{
int n;
cin >> n;
vector<string> v(n, "aaaaaaaaaa");
st.insert(v[0]);
int nxtChange = 0;
for(int i = 1; i < n; i++)
{
string nxtString = v[i - 1];
do
{
char nxtChar = (char) ('a' + rng() % 26);
nxtString[nxtChange] = nxtChar;
} while(bad(nxtString, v[i - 1]));
nxtChange++, nxtChange %= 10;
st.insert(nxtString);
v[i] = nxtString;
}
for(auto &it: v)
cout << it << '\n';
}
signed main()
{
FIO
int T = 1;
// cin >> T;
for(int i = 1; i <= T; i++)
doWork();
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3480kb
input:
5
output:
aaaaaaaaaa yaaaaaaaaa yxaaaaaaaa yxyaaaaaaa yxyhaaaaaa
result:
ok good solution
Test #2:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
3
output:
aaaaaaaaaa uaaaaaaaaa ubaaaaaaaa
result:
ok good solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
4
output:
aaaaaaaaaa iaaaaaaaaa iyaaaaaaaa iybaaaaaaa
result:
ok good solution
Test #4:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
6
output:
aaaaaaaaaa maaaaaaaaa mnaaaaaaaa mnnaaaaaaa mnnnaaaaaa mnnnvaaaaa
result:
ok good solution
Test #5:
score: 0
Accepted
time: 1ms
memory: 3356kb
input:
7
output:
aaaaaaaaaa saaaaaaaaa smaaaaaaaa smvaaaaaaa smvraaaaaa smvrhaaaaa smvrhxaaaa
result:
ok good solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
8
output:
aaaaaaaaaa vaaaaaaaaa vwaaaaaaaa vwzaaaaaaa vwzvaaaaaa vwzvlaaaaa vwzvluaaaa vwzvlukaaa
result:
ok good solution
Test #7:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
9
output:
aaaaaaaaaa laaaaaaaaa liaaaaaaaa linaaaaaaa linqaaaaaa linqcaaaaa linqcpaaaa linqcpqaaa linqcpqiaa
result:
ok good solution
Test #8:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
10
output:
aaaaaaaaaa zaaaaaaaaa zyaaaaaaaa zybaaaaaaa zybraaaaaa zybrvaaaaa zybrvraaaa zybrvrnaaa zybrvrnlaa zybrvrnlqa
result:
ok good solution
Test #9:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
64
output:
aaaaaaaaaa haaaaaaaaa hoaaaaaaaa hohaaaaaaa hohmaaaaaa hohmzaaaaa hohmzpaaaa hohmzpoaaa hohmzpofaa hohmzpofra hohmzpofrw johmzpofrw jghmzpofrw jgymzpofrw jgyqzpofrw jgyqgpofrw jgyqggofrw jgyqggbfrw jgyqggbhrw jgyqggbhjw jgyqggbhja lgyqggbhja lsyqggbhja lsiqggbhja lsiyggbhja lsiypgbhja lsiyphbhja lsi...
result:
ok good solution
Test #10:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
51
output:
aaaaaaaaaa naaaaaaaaa nsaaaaaaaa nsgaaaaaaa nsgsaaaaaa nsgsraaaaa nsgsrmaaaa nsgsrmzaaa nsgsrmzeaa nsgsrmzeoa nsgsrmzeol dsgsrmzeol dvgsrmzeol dvksrmzeol dvkprmzeol dvkpmmzeol dvkpmnzeol dvkpmnteol dvkpmntkol dvkpmntktl dvkpmntkts gvkpmntkts glkpmntkts glfpmntkts glfzmntkts glfzuntkts glfzujtkts glf...
result:
ok good solution
Test #11:
score: 0
Accepted
time: 3ms
memory: 3512kb
input:
97
output:
aaaaaaaaaa eaaaaaaaaa eiaaaaaaaa eiqaaaaaaa eiqvaaaaaa eiqvfaaaaa eiqvfyaaaa eiqvfyjaaa eiqvfyjdaa eiqvfyjdua eiqvfyjdup liqvfyjdup lmqvfyjdup lmivfyjdup lmipfyjdup lmippyjdup lmippwjdup lmippwgdup lmippwgmup lmippwgmhp lmippwgmhr gmippwgmhr gfippwgmhr gfnppwgmhr gfnvpwgmhr gfnvhwgmhr gfnvhogmhr gfn...
result:
ok good solution
Test #12:
score: 0
Accepted
time: 3ms
memory: 3388kb
input:
100
output:
aaaaaaaaaa taaaaaaaaa thaaaaaaaa thkaaaaaaa thklaaaaaa thklsaaaaa thklsdaaaa thklsduaaa thklsduvaa thklsduvha thklsduvhl vhklsduvhl vkklsduvhl vkplsduvhl vkptsduvhl vkptmduvhl vkptmxuvhl vkptmxevhl vkptmxeihl vkptmxeixl vkptmxeixz ikptmxeixz ixptmxeixz ixftmxeixz ixfgmxeixz ixfgfxeixz ixfgfkeixz ixf...
result:
ok good solution
Test #13:
score: 0
Accepted
time: 18ms
memory: 3656kb
input:
1000
output:
aaaaaaaaaa waaaaaaaaa wnaaaaaaaa wnwaaaaaaa wnwvaaaaaa wnwvzaaaaa wnwvzjaaaa wnwvzjgaaa wnwvzjgnaa wnwvzjgnya wnwvzjgnyl qnwvzjgnyl qzwvzjgnyl qzuvzjgnyl qzuczjgnyl qzuckjgnyl qzuckkgnyl qzuckkhnyl qzuckkhdyl qzuckkhdsl qzuckkhdsk azuckkhdsk acuckkhdsk aczckkhdsk aczzkkhdsk aczzukhdsk aczzuchdsk acz...
result:
ok good solution
Test #14:
score: 0
Accepted
time: 18ms
memory: 3648kb
input:
1001
output:
aaaaaaaaaa gaaaaaaaaa gzaaaaaaaa gznaaaaaaa gznbaaaaaa gznbmaaaaa gznbmmaaaa gznbmmxaaa gznbmmxdaa gznbmmxdpa gznbmmxdpl dznbmmxdpl dnnbmmxdpl dndbmmxdpl dndammxdpl dndakmxdpl dndakhxdpl dndakhidpl dndakhifpl dndakhifxl dndakhifxv nndakhifxv nvdakhifxv nvlakhifxv nvlfkhifxv nvlfxhifxv nvlfxaifxv nvl...
result:
ok good solution
Test #15:
score: 0
Accepted
time: 19ms
memory: 3508kb
input:
1024
output:
aaaaaaaaaa uaaaaaaaaa uuaaaaaaaa uubaaaaaaa uubnaaaaaa uubnzaaaaa uubnzmaaaa uubnzmvaaa uubnzmveaa uubnzmveua uubnzmveuq gubnzmveuq gebnzmveuq geinzmveuq geilzmveuq geilkmveuq geilkcveuq geilkcieuq geilkciquq geilkciqnq geilkciqnz ueilkciqnz uyilkciqnz uyulkciqnz uyuvkciqnz uyuviciqnz uyuviliqnz uyu...
result:
ok good solution
Test #16:
score: 0
Accepted
time: 19ms
memory: 3572kb
input:
1025
output:
aaaaaaaaaa qaaaaaaaaa qqaaaaaaaa qqtaaaaaaa qqtraaaaaa qqtrsaaaaa qqtrsmaaaa qqtrsmvaaa qqtrsmveaa qqtrsmveda qqtrsmvedy xqtrsmvedy xctrsmvedy xclrsmvedy xclxsmvedy xclxtmvedy xclxtzvedy xclxtzsedy xclxtzswdy xclxtzswjy xclxtzswjg mclxtzswjg mdlxtzswjg mdextzswjg mdebtzswjg mdebkzswjg mdebkoswjg mde...
result:
ok good solution
Test #17:
score: 0
Accepted
time: 105ms
memory: 3932kb
input:
5000
output:
aaaaaaaaaa qaaaaaaaaa qnaaaaaaaa qntaaaaaaa qntyaaaaaa qntyjaaaaa qntyjpaaaa qntyjpkaaa qntyjpkuaa qntyjpkuda qntyjpkudl sntyjpkudl swtyjpkudl swryjpkudl swrojpkudl swrodpkudl swrodwkudl swrodwzudl swrodwzcdl swrodwzcgl swrodwzcgs owrodwzcgs oirodwzcgs oivodwzcgs oivsdwzcgs oivsuwzcgs oivsuuzcgs oiv...
result:
ok good solution
Test #18:
score: 0
Accepted
time: 104ms
memory: 3848kb
input:
4999
output:
aaaaaaaaaa oaaaaaaaaa ozaaaaaaaa oztaaaaaaa oztkaaaaaa oztknaaaaa oztkneaaaa oztknenaaa oztknenmaa oztknenmza oztknenmzc kztknenmzc kctknenmzc kczknenmzc kczunenmzc kczuvenmzc kczuvunmzc kczuvuamzc kczuvuafzc kczuvuafqc kczuvuafqi bczuvuafqi bazuvuafqi baeuvuafqi baezvuafqi baezcuafqi baezcaafqi bae...
result:
ok good solution
Test #19:
score: 0
Accepted
time: 82ms
memory: 3696kb
input:
4096
output:
aaaaaaaaaa paaaaaaaaa pfaaaaaaaa pftaaaaaaa pfttaaaaaa pfttlaaaaa pfttlxaaaa pfttlxfaaa pfttlxfraa pfttlxfrla pfttlxfrli yfttlxfrli ymttlxfrli ymxtlxfrli ymxjlxfrli ymxjexfrli ymxjemfrli ymxjemxrli ymxjemxbli ymxjemxbxi ymxjemxbxh kmxjemxbxh kwxjemxbxh kwbjemxbxh kwbpemxbxh kwbpimxbxh kwbpitxbxh kwb...
result:
ok good solution
Test #20:
score: 0
Accepted
time: 83ms
memory: 3756kb
input:
4097
output:
aaaaaaaaaa oaaaaaaaaa oxaaaaaaaa oxkaaaaaaa oxklaaaaaa oxklqaaaaa oxklqpaaaa oxklqpmaaa oxklqpmkaa oxklqpmkja oxklqpmkjj rxklqpmkjj rvklqpmkjj rvmlqpmkjj rvmzqpmkjj rvmzjpmkjj rvmzjsmkjj rvmzjsukjj rvmzjsuqjj rvmzjsuqnj rvmzjsuqnv gvmzjsuqnv gmmzjsuqnv gmkzjsuqnv gmksjsuqnv gmksvsuqnv gmksvcuqnv gmk...
result:
ok good solution
Test #21:
score: 0
Accepted
time: 75ms
memory: 3756kb
input:
4098
output:
aaaaaaaaaa maaaaaaaaa mraaaaaaaa mrkaaaaaaa mrkjaaaaaa mrkjoaaaaa mrkjopaaaa mrkjopgaaa mrkjopgdaa mrkjopgdca mrkjopgdcg xrkjopgdcg xzkjopgdcg xzejopgdcg xzedopgdcg xzednpgdcg xzednkgdcg xzednktdcg xzednktocg xzednktovg xzednktovo gzednktovo ghednktovo ghidnktovo ghipnktovo ghipsktovo ghipsztovo ghi...
result:
ok good solution
Test #22:
score: 0
Accepted
time: 75ms
memory: 3768kb
input:
3751
output:
aaaaaaaaaa haaaaaaaaa hmaaaaaaaa hmgaaaaaaa hmgvaaaaaa hmgvqaaaaa hmgvqoaaaa hmgvqodaaa hmgvqodlaa hmgvqodlza hmgvqodlzb emgvqodlzb eagvqodlzb eazvqodlzb eaziqodlzb eazitodlzb eazitedlzb eazitexlzb eazitextzb eazitextob eazitextoz hazitextoz hxzitextoz hxlitextoz hxlotextoz hxlodextoz hxlodsxtoz hxl...
result:
ok good solution