CSES - Aalto Competitive Programming 2024 - wk3 - Wed - Results
Submission details
Task:Spin-Pop-Squeeze-Clap
Sender:aalto2024c_002
Submission time:2024-09-18 16:45:11 +0300
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#10.20 sdetails
#20.82 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.75 sdetails
#72.22 sdetails
#80.68 sdetails
#91.32 sdetails
#101.81 sdetails
#110.77 sdetails
#120.70 sdetails
#131.03 sdetails
#141.33 sdetails
#150.88 sdetails
#160.81 sdetails
#170.88 sdetails
#180.88 sdetails
#191.64 sdetails
#202.16 sdetails
#210.66 sdetails
#220.99 sdetails
#230.87 sdetails
#241.84 sdetails
#250.76 sdetails
#260.70 sdetails
#271.91 sdetails
#280.68 sdetails
#290.69 sdetails
#300.73 sdetails
#310.96 sdetails
#320.73 sdetails
#330.80 sdetails
#342.85 sdetails
#350.83 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:91:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int i = 0; i < s.size(); i++) {
      |                         ~~^~~~~~~~~~
input/code.cpp:117:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int i = 0; i < s.size(); i++) {
      |                         ~~^~~~~~~~~~
input/code.cpp:123:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  123 |         if (s.size() < mx) {
      |             ~~~~~~~~~^~~~
input/code.cpp:128:35: warning: comparison of integer expressions of different signedness: '...

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

string to_string(string s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void debug_out() {
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n, m, mx;
string a, b;

map<string, int> mp;

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> a >> b;
    n = a.size();
    m = b.size();
    mx = max(n, m);

    queue<string> q;
    mp[a] = 0;
    q.push(a);

    auto add = [&](string s, int cur) {
        auto it = mp.find(s);
        if (it == mp.end()) {
            mp[s] = cur + 1;
            q.push(s);
        }
    };

    while (q.size()) {
        string s = q.front();
        q.pop();

        if (s == b) break;

        int cur = mp[s];

        // debug(s, cur);

        // spin
        for (int i = 0; i < s.size(); i++) {
            char tmp = s[i];
            s[i] = b[i];
            add(s, cur);
            s[i] = tmp;

            int num = s[i] - '0';
            for (int sub = -2; sub <= -1; sub++) {
                int cur = (num + sub + 10) % 10;
                char tmp = s[i];
                s[i] = '0' + cur;
                add(s, cur);
                s[i] = tmp;
            }

            // for (char d = '0'; d <= '9'; d++) {
            //     if (c == d) continue;
            //     char tmp = c;
            //     c = d;
            //     add(s, cur);
            //     c = tmp;
            // }
        }

        string ori = s;
        // pop
        for (int i = 0; i < s.size(); i++) {
            s.erase(s.begin() + i);
            add(s, cur);
            s = ori;
        }

        if (s.size() < mx) {
            // squeeze
            for (char d = '0'; d <= '9'; d++) {
                s = d + s;
                add(s, cur);
                for (int i = 0; i < s.size(); i++) {
                    swap(s[i], s[i + 1]);
                    add(s, cur);
                }
                s = ori;
            } 
        }

        // clap
        for (char& c : s) {
            int num = c - '0';
            c = '0' + (num + 1) % 10;
        }
        add(s, cur);
    }

    cout << mp[b] << '\b';
}

Test details

Test 1

Verdict:

input
111222
283303

correct output
4

user output
4

Test 2

Verdict:

input
123123
54545

correct output
4

user output
4

Test 3

Verdict:

input
111
222

correct output
1

user output
1

Test 4

Verdict:

input
999
999

correct output
0

user output
0

Test 5

Verdict:

input
450
57

correct output
2

user output
2

Test 6

Verdict:

input
660487647593824219489241157815...

correct output
674

user output
(empty)

Test 7

Verdict:

input
914177763170669074391500080636...

correct output
130

user output
(empty)

Test 8

Verdict:

input
011524493909266858784005756682...

correct output
681

user output
(empty)

Test 9

Verdict:

input
982597919074833788762328601290...

correct output
717

user output
(empty)

Test 10

Verdict:

input
416721106840388542143044324451...

correct output
215

user output
(empty)

Test 11

Verdict:

input
458073021573681930364262129972...

correct output
473

user output
(empty)

Test 12

Verdict:

input
917400297550473688139849165156...

correct output
699

user output
(empty)

Test 13

Verdict:

input
260181590830166131860913909960...

correct output
584

user output
(empty)

Test 14

Verdict:

input
562301238360777679361730486761...

correct output
284

user output
(empty)

Test 15

Verdict:

input
954220587915890627622301289161...

correct output
416

user output
(empty)

Test 16

Verdict:

input
067903774208751350629566447245...

correct output
442

user output
(empty)

Test 17

Verdict:

input
877893287921742180967929081003...

correct output
358

user output
(empty)

Test 18

Verdict:

input
485260574793809275253093185610...

correct output
442

user output
(empty)

Test 19

Verdict:

input
423232218340629042147624537896...

correct output
192

user output
(empty)

Test 20

Verdict:

input
983444174766143554582284201195...

correct output
83

user output
(empty)

Test 21

Verdict:

input
308023002531575464533553486397...

correct output
984

user output
(empty)

Test 22

Verdict:

input
774637064330445294039402907794...

correct output
544

user output
(empty)

Test 23

Verdict:

input
645428410366485628023288358114...

correct output
378

user output
(empty)

Test 24

Verdict:

input
175337727474341582323359837344...

correct output
695

user output
(empty)

Test 25

Verdict:

input
081836584929414654154099313187...

correct output
493

user output
(empty)

Test 26

Verdict:

input
241592066112579763355561876139...

correct output
630

user output
(empty)

Test 27

Verdict:

input
664737828830059612330669705871...

correct output
559

user output
(empty)

Test 28

Verdict:

input
230972151340592860909446321989...

correct output
696

user output
(empty)

Test 29

Verdict:

input
410946685234703970117608650309...

correct output
691

user output
(empty)

Test 30

Verdict:

input
692323212407710827747149254185...

correct output
536

user output
(empty)

Test 31

Verdict:

input
034704049619193895285878119956...

correct output
467

user output
(empty)

Test 32

Verdict:

input
336980270982636303223976539004...

correct output
543

user output
(empty)

Test 33

Verdict:

input
744311485456233719196607507429...

correct output
570

user output
(empty)

Test 34

Verdict:

input
289232763326229330631165228849...

correct output
563

user output
(empty)

Test 35

Verdict:

input
159941856600173517598637236698...

correct output
431

user output
(empty)