QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#529071#1361. Ant TypingStayAloneAC ✓284ms4044kbC++141.9kb2024-08-24 08:52:202024-08-24 08:52:21

Judging History

This is the latest submission verdict.

  • [2024-08-24 08:52:21]
  • Judged
  • Verdict: AC
  • Time: 284ms
  • Memory: 4044kb
  • [2024-08-24 08:52:20]
  • Submitted

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'