QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#529071 | #1361. Ant Typing | StayAlone | AC ✓ | 284ms | 4044kb | C++14 | 1.9kb | 2024-08-24 08:52:20 | 2024-08-24 08:52:21 |
Judging History
answer
#include <bits/stdc++.h>
#define rep1(i, l, r) for (int i = l; i <= int(r); ++i)
#define rep2(i, l, r) for (int i = l; i >= int(r); --i)
#define rer(i, l, r, a) rep1(i, l, r) read(a[i])
#define ptc putchar
#define il inline
#define eb emplace_back
#define ef emplace_front
#define mp make_pair
#define fst first
#define snd second
#define sqr(x) ((x) * (x))
#define ls(x) x << 1
#define rs(x) x << 1 | 1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 bll;
// typedef unsigned __int128 ubll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5 + 10, LOGN = log2(MAXN) + 1, inf = ~0U >> 2, INF = ~0U >> 1;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
namespace stupid_lrc {
template <typename T> il bool read(T &x) {
x = 0; bool f = false; char ch;
while (!isdigit(ch = getchar())) {
f ^= !(ch ^ '-');
if (ch == EOF) return false;
}
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
if (f) x = ~x + 1; return true;
}
il int read() {int x; read(x); return x;}
template <typename T> il bool read(pair <T, T> &x) {return read(x.fst) && read(x.snd);}
template <typename T> il void gmin(T &x, T y) {x = x < y ? x : y;}
template <typename T> il void gmax(T &x, T y) {x = x > y ? x : y;}
template <typename T, typename ...L>
il bool read(T &x, L &...y) {return read(x) && read(y...);}
template <typename T> il T lowbit(const T &x) {return x & -x;}
}
using namespace stupid_lrc;
char s[MAXN];
int n, ans = inf, cnt[10][10], pos[10];
int main() {
scanf("%s", s + 1); n = strlen(s + 1);
rep1(i, 1, n - 1) ++cnt[s[i] - '0'][s[i + 1] - '0'];
rep1(i, 0, 9) pos[i] = i;
do {
int now = pos[s[1] - '0'];
rep1(i, 0, 9) rep1(j, 0, 9) now += cnt[i][j] * abs(pos[i] - pos[j]);
gmin(ans, now);
} while (next_permutation(pos, pos + 10));
printf("%d", ans + n);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 279ms
memory: 3832kb
input:
6
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 284ms
memory: 3988kb
input:
352836512461179399826927828445163785261417666171453483576899676763764928341261962358737253818463814858565221466575498899898835568743316628247174676952381449147193191788177911797527361649543158616436321694172452689147288835568666918784929695569394655833978219612584637258492511247969998253315177569943...
output:
392933
result:
ok single line: '392933'
Test #3:
score: 0
Accepted
time: 284ms
memory: 3848kb
input:
968884598119167786222882717561136271258178322114499631431168437152319338284128325566492371843153634373998119972663175955316621871196955773794711869424245474973253727335485699826672425921549421474494147229652553728521332495721653457163161741649486568718788497235884884271122261183582319332269114971817...
output:
394664
result:
ok single line: '394664'
Test #4:
score: 0
Accepted
time: 282ms
memory: 4008kb
input:
683412251689845461817923147259774964383159658449891915133215549956251828864364313696312963272819495298632848747431585341886467284794396545668622674767116477954324211934265166678211817468916142924319716576862979237997215273147359445833376466319214969265971711816157481253512934953386353547377361396196...
output:
393919
result:
ok single line: '393919'
Test #5:
score: 0
Accepted
time: 284ms
memory: 3800kb
input:
793413248661841899956962996149582153286568745845426726626741997574977847728465587437749642293284475574432875453315117193156379221656595692327291876139928696877762933239918113828226436292619542275425269336822184239426865136177559755975137675165562357892872597995857677171316858612137827928654836578312...
output:
393800
result:
ok single line: '393800'
Test #6:
score: 0
Accepted
time: 283ms
memory: 3996kb
input:
417945123165992614765338944444296975768196599265132553568932179127253855711163863765928951248227823968765833275116543283633468248662742363347291168368263991438531662944563875763722861928627934312432227281273297129383518712815967362374683269769633684932228244154481357479667523356385974327797382399565...
output:
393463
result:
ok single line: '393463'
Test #7:
score: 0
Accepted
time: 284ms
memory: 4008kb
input:
761516338356551975157774489286685265387439119927746187735157324467763246485133173342627781962263755596343666343884382465193163361936949619496665752933335714897716429375772618157582373867283283241418469738176736798731116515132727471419652997699517743927634878619359762879346214965527473515198792719195...
output:
393734
result:
ok single line: '393734'
Test #8:
score: 0
Accepted
time: 283ms
memory: 4044kb
input:
452646533999964766974591119414915157862638483746513612496323887667364175241679367348981649871647174262463497116677212838644661788747989751984334147364683635749881659943383248733477481144973282945443365529669337986546236169645654786951236661879848964251181798394453699395876173261855611628215186596864...
output:
393449
result:
ok single line: '393449'
Test #9:
score: 0
Accepted
time: 283ms
memory: 4000kb
input:
892933166787684876233472692156924877315491587224215657794711176246792498827395714358785444393137862131622236664777297685973478453481742735955935812548619939949816263513262474652489599115938517554462282656168899394675812293721799857276432796467622182215326836428112463683881984867759968618983979294471...
output:
393543
result:
ok single line: '393543'
Test #10:
score: 0
Accepted
time: 282ms
memory: 4044kb
input:
443494391473867598146699249145491138796297424237949566864711424981515755661718517795236754493356987316553369681157821636124825155655178124138485945376482389189885549849534358284722459348434263344632142928463753398997552947717347367229653393645997599977962716972387584965662667771286366458526719422475...
output:
393892
result:
ok single line: '393892'
Test #11:
score: 0
Accepted
time: 280ms
memory: 3996kb
input:
731751822859611165598229768362525618797797786414166541796193792191817827787177438958755714113769658417884754281628475364174221136483412233629911963258152989777957187848636623359446872443865864688396641842338556377493828515381262475482145412849119644181582598812122977861578955553151553678661841713618...
output:
395302
result:
ok single line: '395302'
Test #12:
score: 0
Accepted
time: 279ms
memory: 4004kb
input:
934538585471192519625275252367341866598775944166724559493147921744372875426231194623428159714745149887834583134911937786184781872397328363525511548593914512334184721543963296931746111262678356446331416657852779338592196754945219987351255255113871941424453534388598429896133627862518823496499552773293...
output:
394207
result:
ok single line: '394207'
Test #13:
score: 0
Accepted
time: 283ms
memory: 3924kb
input:
555458514559312987914285792461913388993893412631869484867557593593525819593167492862232364752163342551675643529457597173941389569895113199149129217845486619926653726231667241256957632199264546637842377666942866821631564188222544636553744594511762271883887995884588548164211188283798612313524714389853...
output:
393360
result:
ok single line: '393360'
Test #14:
score: 0
Accepted
time: 282ms
memory: 3988kb
input:
443311794878596951273565853645197445255454363672495881798126447715765388831543847213671343257665541858544398361698142261622689885464777244736891361542468382554323887898376413472285718763828126796623771187213266973727697493572839135445921379295646449329819692475718229886945353998585854198272694653781...
output:
393589
result:
ok single line: '393589'
Test #15:
score: 0
Accepted
time: 282ms
memory: 3704kb
input:
6666666666111212131313141414141515151515161616161616171717171717171818181818181818191919191919191919
output:
283
result:
ok single line: '283'
Test #16:
score: 0
Accepted
time: 278ms
memory: 3704kb
input:
111212131313141414141515151515161616161616171717171717171818181818181818191919191919191919
output:
273
result:
ok single line: '273'