Käännöt

input/code.cpp: In function 'void check()':
input/code.cpp:187:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |             for (int i = 0; i < a.size(); ++i) {
      |                             ~~^~~~~~~~~~
input/code.cpp:191:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |                 if (i == a.size() - 1) cout << "}";
      |                     ~~^~~~~~~~~~~~~~~
input/code.cpp:199:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |             for (int i = 0; i < b.size(); ++i) {
      |                             ~~^~~~~~~~~~
input/code.cpp:203:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<in...

#include <bits/stdc++.h>

using namespace std;
 
void init_code() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
 
bool is_ok(int j, int i, int n, int k) {
    if (j < 1 || (j + (k - 1)) > n || j < i) {
        return false;
    }
 
    return true;
}
 
void rev(int i, int k, vector<int>& a, vector<int>& pos, vector<int>& res) {
    reverse(a.begin() + i, a.begin() + i + k);
 
    for (int ik = 0; ik <= k - 1; ++ik) {
        pos[a[i + ik]] = i + ik;
    }
 
    res.push_back(i);
}
 
vector<int> compress(vector<int>& a) {
    vector<int> b = a;
 
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
 
    for (int &x : a)
        x = int(lower_bound(b.begin(), b.end(), x) - b.begin()) + 1;
 
    return a;
}

vector<int> solve2(int n, int k, vector<int> a) {
    queue<vector<int>>  q;
    q.push(a);

    map<vector<int>, int> d;
    d[a] = 0;

    map<vector<int>, vector<int>> prev;
    
    map<vector<int>, int> prev_op;
    prev_op[a] = -1;
    while (!q.empty()) {
        vector<int> v = q.front();
        q.pop();

        /*if (d[v] > 10) {
            break;
        }*/

        if (v[0] == 1) {
            //cout << d[v] << '\n';
            
            vector<int> ops;
            while (prev_op[v] != -1) {
                ops.push_back(prev_op[v] + 1);
                v = prev[v];
            }

            reverse(ops.begin(), ops.end());

            return ops;
        }

        for (int i = 0; i < n - (k - 1); ++i) {
            vector<int> next = v;
            reverse(next.begin() + i, next.begin() + i + k);
            if (!d.count(next) || d[next] > d[v] + 1) {
                q.push(next);
                prev[next] = v;
                prev_op[next] = i;
                d[next] = d[v] + 1;
            }
        }
    }

    return vector<int> {-1};
}

 
vector<int> solve(int n, int k, vector<int> a) {
    a.insert(a.begin(), -1);

    vector<int> pos(n + 1);
    for (int i = 1; i <= n; ++i) {
        pos[a[i]] = i;
    }

    vector<int> res;
 
    if (a[1] == 1) {
        return vector<int> {-1};
    }
     
    /*if (n <= 8) {
        a.erase(a.begin());
 
        res = solve2(n, k, a);

        return res;
    }*/
 
    for (int i = 1; i <= 1; ++i) {
        int j = pos[i];
        
        vector<int> fix;
        if ((j - i) % (k - 1) != 0) {
            queue<pair<vector<int>, int>> q;    
            q.push({vector<int> (), j});
 
            int x = 0;
            while (!q.empty() && x <= 10) {
                vector<int> op = q.front().first;
                int cur_j = q.front().second;
 
                q.pop();
 
                if (cur_j < i) {
                    continue;
                }
 
                if ((cur_j - i) % (k - 1) == 0) {
                    fix = op;
                    break;
                }
 
                for (int it = cur_j - (k - 1); it <= cur_j; ++it) {
                    if (is_ok(it, i, n, k)) {
                        op.push_back(it);
                        int new_j = it + k - (abs(cur_j - it) + 1);
                        q.push({op, new_j});
                        op.pop_back();
                        x++;
                    }
                }
            }
        }
        
        for (auto it : fix) {
            rev(it, k, a, pos, res);
        }
        
        j = pos[i];
 
        if ((j - i) % (k - 1) == 0) {
            while (j != i) {
                rev(j - (k - 1), k, a, pos, res);
                j -= (k - 1);
            }
        } else {
            break;
        }
    }

    if (a[1] == 1) return res;

    return vector<int> {-1};
}


void check() {
    int n = 8, k = 5;

    vector<int> a(n);

    iota(a.begin(), a.end(), 1);

    int t = 0;
    do {
        //random_shuffle(a.begin(), a.end());

        vector<int> b = solve(n, k, a);
        if (b.size() > 0 && b[0] != -1) {
            cout << "mp[";
            for (int i = 0; i < a.size(); ++i) {
                if (i == 0) cout << "{";
                cout << a[i];
                //cout << ' ';
                if (i == a.size() - 1) cout << "}";
                else cout << ", ";
            }
            //cout << '\n';
            //cout << b.size() << '\n';
            
            cout << "] = ";
            
            for (int i = 0; i < b.size(); ++i) {
                if (i == 0) cout << "{";
                cout << b[i];
                //cout << ' ';
                if (i == b.size() - 1) cout << "}";
                else cout << ", ";
            }
            //cout << '\n';
            cout << ";\n";
        }
        t++;
    } while (next_permutation(a.begin(), a.end()));  
}

signed main() {
    init_code();
    int t = 1;
    // cin >> t;
    while (t--) {
        check();
        //solve();
    }
    return 0;
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 2

Verdict: WRONG ANSWER

Test 12

Group: 2

Verdict: WRONG ANSWER

Test 13

Group: 2

Verdict: WRONG ANSWER

Test 14

Group: 2

Verdict: WRONG ANSWER

Test 15

Group: 2

Verdict: WRONG ANSWER

Test 16

Group: 2

Verdict: WRONG ANSWER

Test 17

Group: 3

Verdict: WRONG ANSWER

Test 18

Group: 3

Verdict: WRONG ANSWER

Test 19

Group: 3

Verdict: WRONG ANSWER

Test 20

Group: 3

Verdict: WRONG ANSWER

Test 21

Group: 3

Verdict: WRONG ANSWER

Test 22

Group: 3

Verdict: WRONG ANSWER

Test 23

Group: 3

Verdict: WRONG ANSWER

Test 24

Group: 3

Verdict: WRONG ANSWER

Test 25

Group: 3

Verdict: WRONG ANSWER

Test 26

Group: 4

Verdict: WRONG ANSWER

Test 27

Group: 4

Verdict: WRONG ANSWER

Test 28

Group: 4

Verdict: WRONG ANSWER

Test 29

Group: 4

Verdict: WRONG ANSWER

Test 30

Group: 4

Verdict: WRONG ANSWER

Test 31

Group: 4

Verdict: WRONG ANSWER

Test 32

Group: 4

Verdict: WRONG ANSWER

Test 33

Group: 4

Verdict: WRONG ANSWER

Test 34

Group: 4

Verdict: WRONG ANSWER