QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99009 | #4237. Word Ladder | Zuqa | AC ✓ | 101ms | 3872kb | C++20 | 1.8kb | 2023-04-21 08:35:30 | 2023-04-21 08:35:31 |
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)
{
if(s == prv)
return true;
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: 3356kb
input:
5
output:
aaaaaaaaaa oaaaaaaaaa oeaaaaaaaa oegaaaaaaa oeghaaaaaa
result:
ok good solution
Test #2:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
3
output:
aaaaaaaaaa faaaaaaaaa fwaaaaaaaa
result:
ok good solution
Test #3:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
4
output:
aaaaaaaaaa laaaaaaaaa lbaaaaaaaa lbpaaaaaaa
result:
ok good solution
Test #4:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
6
output:
aaaaaaaaaa maaaaaaaaa muaaaaaaaa mutaaaaaaa mutxaaaaaa mutxvaaaaa
result:
ok good solution
Test #5:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
7
output:
aaaaaaaaaa daaaaaaaaa dbaaaaaaaa dbbaaaaaaa dbbuaaaaaa dbbupaaaaa dbbupqaaaa
result:
ok good solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
8
output:
aaaaaaaaaa xaaaaaaaaa xtaaaaaaaa xtfaaaaaaa xtfdaaaaaa xtfdlaaaaa xtfdlfaaaa xtfdlfiaaa
result:
ok good solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
9
output:
aaaaaaaaaa waaaaaaaaa wvaaaaaaaa wvdaaaaaaa wvddaaaaaa wvddwaaaaa wvddwvaaaa wvddwvzaaa wvddwvzbaa
result:
ok good solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
10
output:
aaaaaaaaaa gaaaaaaaaa guaaaaaaaa gucaaaaaaa guclaaaaaa guclraaaaa guclrbaaaa guclrblaaa guclrblxaa guclrblxra
result:
ok good solution
Test #9:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
64
output:
aaaaaaaaaa qaaaaaaaaa qkaaaaaaaa qktaaaaaaa qktsaaaaaa qktsjaaaaa qktsjcaaaa qktsjclaaa qktsjclyaa qktsjclyga qktsjclygu mktsjclygu mntsjclygu mnesjclygu mneljclygu mnelqclygu mnelqglygu mnelqgoygu mnelqgopgu mnelqgopcu mnelqgopci xnelqgopci xqelqgopci xqylqgopci xqymqgopci xqymvgopci xqymvmopci xqy...
result:
ok good solution
Test #10:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
51
output:
aaaaaaaaaa caaaaaaaaa cjaaaaaaaa cjhaaaaaaa cjhxaaaaaa cjhxtaaaaa cjhxtiaaaa cjhxtiqaaa cjhxtiqjaa cjhxtiqjfa cjhxtiqjfv rjhxtiqjfv rihxtiqjfv ripxtiqjfv riphtiqjfv riphaiqjfv riphanqjfv riphanvjfv riphanvtfv riphanvtyv riphanvtyf oiphanvtyf onphanvtyf onvhanvtyf onvcanvtyf onvcynvtyf onvcyxvtyf onv...
result:
ok good solution
Test #11:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
97
output:
aaaaaaaaaa baaaaaaaaa bsaaaaaaaa bswaaaaaaa bswwaaaaaa bswwbaaaaa bswwbuaaaa bswwbufaaa bswwbufhaa bswwbufhba bswwbufhbu vswwbufhbu vpwwbufhbu vptwbufhbu vptdbufhbu vptdfufhbu vptdfmfhbu vptdfmbhbu vptdfmbxbu vptdfmbxcu vptdfmbxcb gptdfmbxcb gutdfmbxcb guldfmbxcb gullfmbxcb gullnmbxcb gullnxbxcb gul...
result:
ok good solution
Test #12:
score: 0
Accepted
time: 3ms
memory: 3476kb
input:
100
output:
aaaaaaaaaa caaaaaaaaa cfaaaaaaaa cfhaaaaaaa cfhbaaaaaa cfhbnaaaaa cfhbnkaaaa cfhbnkraaa cfhbnkrvaa cfhbnkrvga cfhbnkrvgp jfhbnkrvgp jshbnkrvgp jsebnkrvgp jsexnkrvgp jsexdkrvgp jsexdcrvgp jsexdctvgp jsexdctrgp jsexdctrwp jsexdctrwz vsexdctrwz veexdctrwz venxdctrwz venqdctrwz venqmctrwz venqmvtrwz ven...
result:
ok good solution
Test #13:
score: 0
Accepted
time: 19ms
memory: 3612kb
input:
1000
output:
aaaaaaaaaa waaaaaaaaa wjaaaaaaaa wjxaaaaaaa wjxkaaaaaa wjxkoaaaaa wjxkocaaaa wjxkockaaa wjxkocknaa wjxkocknha wjxkocknhi ajxkocknhi axxkocknhi axckocknhi axcuocknhi axculcknhi axculmknhi axculmanhi axculmaihi axculmaici axculmaicf qxculmaicf qfculmaicf qfqulmaicf qfqxlmaicf qfqxrmaicf qfqxrtaicf qfq...
result:
ok good solution
Test #14:
score: 0
Accepted
time: 18ms
memory: 3468kb
input:
1001
output:
aaaaaaaaaa haaaaaaaaa hiaaaaaaaa hiqaaaaaaa hiqcaaaaaa hiqchaaaaa hiqchuaaaa hiqchuyaaa hiqchuybaa hiqchuybta hiqchuybtd ziqchuybtd znqchuybtd znxchuybtd znxjhuybtd znxjouybtd znxjojybtd znxjojgbtd znxjojgrtd znxjojgrsd znxjojgrsv fnxjojgrsv fuxjojgrsv fubjojgrsv fubbojgrsv fubbqjgrsv fubbqggrsv fub...
result:
ok good solution
Test #15:
score: 0
Accepted
time: 18ms
memory: 3572kb
input:
1024
output:
aaaaaaaaaa naaaaaaaaa nvaaaaaaaa nvraaaaaaa nvriaaaaaa nvrijaaaaa nvrijbaaaa nvrijbdaaa nvrijbdbaa nvrijbdbha nvrijbdbhw jvrijbdbhw jorijbdbhw jovijbdbhw jovajbdbhw jovaobdbhw jovaosdbhw jovaosibhw jovaosihhw jovaosihlw jovaosihli tovaosihli thvaosihli thbaosihli thbwosihli thbwwsihli thbwwiihli thb...
result:
ok good solution
Test #16:
score: 0
Accepted
time: 19ms
memory: 3548kb
input:
1025
output:
aaaaaaaaaa iaaaaaaaaa iqaaaaaaaa iqraaaaaaa iqrxaaaaaa iqrxeaaaaa iqrxekaaaa iqrxekkaaa iqrxekkeaa iqrxekkeda iqrxekkedu rqrxekkedu rwrxekkedu rwfxekkedu rwfmekkedu rwfmtkkedu rwfmtlkedu rwfmtloedu rwfmtlopdu rwfmtlopzu rwfmtlopzo iwfmtlopzo iofmtlopzo ioumtlopzo ioultlopzo ioulvlopzo ioulvbopzo iou...
result:
ok good solution
Test #17:
score: 0
Accepted
time: 97ms
memory: 3852kb
input:
5000
output:
aaaaaaaaaa caaaaaaaaa chaaaaaaaa chhaaaaaaa chhcaaaaaa chhcpaaaaa chhcpyaaaa chhcpymaaa chhcpymdaa chhcpymdja chhcpymdjz phhcpymdjz pfhcpymdjz pfycpymdjz pfyrpymdjz pfyrjymdjz pfyrjrmdjz pfyrjredjz pfyrjrerjz pfyrjrervz pfyrjrervu kfyrjrervu ksyrjrervu ksdrjrervu ksdgjrervu ksdgfrervu ksdgfpervu ksd...
result:
ok good solution
Test #18:
score: 0
Accepted
time: 101ms
memory: 3768kb
input:
4999
output:
aaaaaaaaaa saaaaaaaaa swaaaaaaaa swlaaaaaaa swlfaaaaaa swlfwaaaaa swlfwhaaaa swlfwhlaaa swlfwhlmaa swlfwhlmxa swlfwhlmxz hwlfwhlmxz hslfwhlmxz hspfwhlmxz hspnwhlmxz hspnghlmxz hspngvlmxz hspngvpmxz hspngvppxz hspngvppaz hspngvppav yspngvppav yppngvppav yprngvppav yprjgvppav yprjivppav yprjijppav ypr...
result:
ok good solution
Test #19:
score: 0
Accepted
time: 81ms
memory: 3696kb
input:
4096
output:
aaaaaaaaaa laaaaaaaaa lraaaaaaaa lrxaaaaaaa lrxraaaaaa lrxrfaaaaa lrxrfiaaaa lrxrfiwaaa lrxrfiwwaa lrxrfiwwoa lrxrfiwwob hrxrfiwwob hhxrfiwwob hhnrfiwwob hhnmfiwwob hhnmtiwwob hhnmtcwwob hhnmtciwob hhnmtcibob hhnmtcibfb hhnmtcibfm qhnmtcibfm qjnmtcibfm qjtmtcibfm qjtntcibfm qjtnccibfm qjtncdibfm qjt...
result:
ok good solution
Test #20:
score: 0
Accepted
time: 82ms
memory: 3788kb
input:
4097
output:
aaaaaaaaaa haaaaaaaaa hlaaaaaaaa hlwaaaaaaa hlwoaaaaaa hlwooaaaaa hlwoosaaaa hlwoosxaaa hlwoosxlaa hlwoosxlka hlwoosxlkr elwoosxlkr egwoosxlkr egpoosxlkr egpzosxlkr egpzcsxlkr egpzcaxlkr egpzcawlkr egpzcawxkr egpzcawxyr egpzcawxyh ygpzcawxyh yvpzcawxyh yvzzcawxyh yvzjcawxyh yvzjfawxyh yvzjfhwxyh yvz...
result:
ok good solution
Test #21:
score: 0
Accepted
time: 82ms
memory: 3716kb
input:
4098
output:
aaaaaaaaaa oaaaaaaaaa oxaaaaaaaa oxnaaaaaaa oxnzaaaaaa oxnzraaaaa oxnzrfaaaa oxnzrftaaa oxnzrftxaa oxnzrftxda oxnzrftxde xxnzrftxde xmnzrftxde xmczrftxde xmcnrftxde xmcnuftxde xmcnudtxde xmcnudcxde xmcnudclde xmcnudclhe xmcnudclhm vmcnudclhm vkcnudclhm vkanudclhm vkayudclhm vkaygdclhm vkaygcclhm vka...
result:
ok good solution
Test #22:
score: 0
Accepted
time: 73ms
memory: 3872kb
input:
3751
output:
aaaaaaaaaa uaaaaaaaaa ueaaaaaaaa uecaaaaaaa ueceaaaaaa uecejaaaaa uecejqaaaa uecejqdaaa uecejqdvaa uecejqdvta uecejqdvtx kecejqdvtx kgcejqdvtx kgdejqdvtx kgdwjqdvtx kgdwaqdvtx kgdwaedvtx kgdwaejvtx kgdwaejptx kgdwaejpmx kgdwaejpmm ygdwaejpmm yndwaejpmm yntwaejpmm yntsaejpmm yntstejpmm yntstqjpmm ynt...
result:
ok good solution