oj.uz

Submission #274884

# Submission time Handle Problem Language Result Execution time Memory
274884 2020-08-19T19:39:04 Z index_ Lock Puzzle (innopolis2018_final_A) C++14
89 / 100
 74 ms 760 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <chrono>
#include <cassert>
#include <bitset>
#include <random>

using namespace std;

typedef long long li;
typedef  long double ld;
const li MAX = 3e5 + 5;

li inf = (li)3000000000;
li mod = (li)998244353;

li n, m;
string s, t;

void swp(li len) {
    string a, b;
    a = s;
    for (int i = 0; i < len; i++) {
        b.push_back(a.back());
        a.pop_back();
    }
    s = b + a;
}

void pos() {
    string a, b;
    a = s;
    b = t;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if (a != b) {
        cout << -1;
        exit(0);
    }

}

void solve() {

    cin >> n >> m;
    cin >> s >> t;
    pos();
    vector<li> ans;
    for (int i = 0; i < n; i++) {
        li ind;
        for (int j = i; j < n; j++) {
            if (s[j] == t[i]) {
                ind = j;
                break;
            }
        }
        swp(n);
        swp(ind);
        swp(1);
        ans.push_back(n);
        ans.push_back(ind);
        ans.push_back(1);
    }
    swp(n);
    ans.push_back(n);
    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";

}


int main() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios::sync_with_stdio(0);
    li q;
    q = 1;
    while (q--) solve();

    return 0;
}

Compilation message

A.cpp: In function 'void solve()':
A.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
      |                     ~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB [n = 1, m = 10000], OK, 4 operations
2 Correct 1 ms 384 KB [n = 2, m = 10000], OK, 7 operations
3 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
4 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
5 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
6 Correct 0 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 0 ms 384 KB [n = 8, m = 10000], OK, 25 operations
8 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB [n = 1, m = 10000], OK, 4 operations
2 Correct 1 ms 384 KB [n = 2, m = 10000], OK, 7 operations
3 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
4 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
5 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
6 Correct 0 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 0 ms 384 KB [n = 8, m = 10000], OK, 25 operations
8 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
9 Correct 1 ms 256 KB [n = 49, m = 10000], OK, 148 operations
10 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
11 Correct 1 ms 384 KB [n = 100, m = 10000], OK, 301 operations
12 Correct 1 ms 384 KB [n = 99, m = 10000], OK, 298 operations
13 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
14 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
15 Correct 1 ms 384 KB [n = 50, m = 10000], OK: No solution
16 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
17 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB [n = 1, m = 10000], OK, 4 operations
2 Correct 1 ms 384 KB [n = 2, m = 10000], OK, 7 operations
3 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
4 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
5 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
6 Correct 0 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 0 ms 384 KB [n = 8, m = 10000], OK, 25 operations
8 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
9 Correct 1 ms 256 KB [n = 49, m = 10000], OK, 148 operations
10 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
11 Correct 1 ms 384 KB [n = 100, m = 10000], OK, 301 operations
12 Correct 1 ms 384 KB [n = 99, m = 10000], OK, 298 operations
13 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
14 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
15 Correct 1 ms 384 KB [n = 50, m = 10000], OK: No solution
16 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
17 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
18 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
19 Correct 19 ms 384 KB [n = 999, m = 10000], OK, 2998 operations
20 Correct 20 ms 384 KB [n = 998, m = 10000], OK, 2995 operations
21 Correct 19 ms 384 KB [n = 997, m = 10000], OK, 2992 operations
22 Correct 20 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
23 Correct 21 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
24 Correct 1 ms 384 KB [n = 1000, m = 10000], OK: No solution
25 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
26 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB [n = 1, m = 10000], OK, 4 operations
2 Correct 1 ms 384 KB [n = 2, m = 10000], OK, 7 operations
3 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
4 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
5 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
6 Correct 0 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 0 ms 384 KB [n = 8, m = 10000], OK, 25 operations
8 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
9 Correct 1 ms 256 KB [n = 49, m = 10000], OK, 148 operations
10 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
11 Correct 1 ms 384 KB [n = 100, m = 10000], OK, 301 operations
12 Correct 1 ms 384 KB [n = 99, m = 10000], OK, 298 operations
13 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
14 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
15 Correct 1 ms 384 KB [n = 50, m = 10000], OK: No solution
16 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
17 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
18 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
19 Correct 19 ms 384 KB [n = 999, m = 10000], OK, 2998 operations
20 Correct 20 ms 384 KB [n = 998, m = 10000], OK, 2995 operations
21 Correct 19 ms 384 KB [n = 997, m = 10000], OK, 2992 operations
22 Correct 20 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
23 Correct 21 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
24 Correct 1 ms 384 KB [n = 1000, m = 10000], OK: No solution
25 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
26 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
27 Correct 70 ms 452 KB [n = 2000, m = 10000], OK, 6001 operations
28 Correct 69 ms 504 KB [n = 1999, m = 10000], OK, 5998 operations
29 Correct 68 ms 504 KB [n = 1998, m = 10000], OK, 5995 operations
30 Correct 69 ms 504 KB [n = 1997, m = 10000], OK, 5992 operations
31 Correct 68 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
32 Correct 70 ms 524 KB [n = 2000, m = 10000], OK, 6001 operations
33 Correct 1 ms 384 KB [n = 2000, m = 10000], OK: No solution
34 Correct 69 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
35 Correct 70 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB [n = 1, m = 10000], OK, 4 operations
2 Correct 1 ms 384 KB [n = 2, m = 10000], OK, 7 operations
3 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
4 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
5 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
6 Correct 0 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 0 ms 384 KB [n = 8, m = 10000], OK, 25 operations
8 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
9 Correct 1 ms 256 KB [n = 49, m = 10000], OK, 148 operations
10 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
11 Correct 1 ms 384 KB [n = 100, m = 10000], OK, 301 operations
12 Correct 1 ms 384 KB [n = 99, m = 10000], OK, 298 operations
13 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
14 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
15 Correct 1 ms 384 KB [n = 50, m = 10000], OK: No solution
16 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
17 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
18 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
19 Correct 19 ms 384 KB [n = 999, m = 10000], OK, 2998 operations
20 Correct 20 ms 384 KB [n = 998, m = 10000], OK, 2995 operations
21 Correct 19 ms 384 KB [n = 997, m = 10000], OK, 2992 operations
22 Correct 20 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
23 Correct 21 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
24 Correct 1 ms 384 KB [n = 1000, m = 10000], OK: No solution
25 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
26 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
27 Correct 70 ms 452 KB [n = 2000, m = 10000], OK, 6001 operations
28 Correct 69 ms 504 KB [n = 1999, m = 10000], OK, 5998 operations
29 Correct 68 ms 504 KB [n = 1998, m = 10000], OK, 5995 operations
30 Correct 69 ms 504 KB [n = 1997, m = 10000], OK, 5992 operations
31 Correct 68 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
32 Correct 70 ms 524 KB [n = 2000, m = 10000], OK, 6001 operations
33 Correct 1 ms 384 KB [n = 2000, m = 10000], OK: No solution
34 Correct 69 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
35 Correct 70 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
36 Correct 69 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
37 Correct 70 ms 632 KB [n = 1999, m = 8100], OK, 5998 operations
38 Correct 68 ms 504 KB [n = 1998, m = 8100], OK, 5995 operations
39 Correct 73 ms 504 KB [n = 1997, m = 8100], OK, 5992 operations
40 Correct 69 ms 512 KB [n = 1996, m = 8100], OK, 5989 operations
41 Correct 68 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
42 Correct 70 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
43 Correct 1 ms 384 KB [n = 2000, m = 8100], OK: No solution
44 Correct 74 ms 436 KB [n = 2000, m = 8100], OK, 6001 operations
45 Correct 69 ms 508 KB [n = 2000, m = 8100], OK, 6001 operations

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB [n = 1, m = 10000], OK, 4 operations
2 Correct 1 ms 384 KB [n = 2, m = 10000], OK, 7 operations
3 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
4 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
5 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
6 Correct 0 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 0 ms 384 KB [n = 8, m = 10000], OK, 25 operations
8 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
9 Correct 1 ms 256 KB [n = 49, m = 10000], OK, 148 operations
10 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
11 Correct 1 ms 384 KB [n = 100, m = 10000], OK, 301 operations
12 Correct 1 ms 384 KB [n = 99, m = 10000], OK, 298 operations
13 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
14 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
15 Correct 1 ms 384 KB [n = 50, m = 10000], OK: No solution
16 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
17 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
18 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
19 Correct 19 ms 384 KB [n = 999, m = 10000], OK, 2998 operations
20 Correct 20 ms 384 KB [n = 998, m = 10000], OK, 2995 operations
21 Correct 19 ms 384 KB [n = 997, m = 10000], OK, 2992 operations
22 Correct 20 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
23 Correct 21 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
24 Correct 1 ms 384 KB [n = 1000, m = 10000], OK: No solution
25 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
26 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
27 Correct 70 ms 452 KB [n = 2000, m = 10000], OK, 6001 operations
28 Correct 69 ms 504 KB [n = 1999, m = 10000], OK, 5998 operations
29 Correct 68 ms 504 KB [n = 1998, m = 10000], OK, 5995 operations
30 Correct 69 ms 504 KB [n = 1997, m = 10000], OK, 5992 operations
31 Correct 68 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
32 Correct 70 ms 524 KB [n = 2000, m = 10000], OK, 6001 operations
33 Correct 1 ms 384 KB [n = 2000, m = 10000], OK: No solution
34 Correct 69 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
35 Correct 70 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
36 Correct 69 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
37 Correct 70 ms 632 KB [n = 1999, m = 8100], OK, 5998 operations
38 Correct 68 ms 504 KB [n = 1998, m = 8100], OK, 5995 operations
39 Correct 73 ms 504 KB [n = 1997, m = 8100], OK, 5992 operations
40 Correct 69 ms 512 KB [n = 1996, m = 8100], OK, 5989 operations
41 Correct 68 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
42 Correct 70 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
43 Correct 1 ms 384 KB [n = 2000, m = 8100], OK: No solution
44 Correct 74 ms 436 KB [n = 2000, m = 8100], OK, 6001 operations
45 Correct 69 ms 508 KB [n = 2000, m = 8100], OK, 6001 operations
46 Correct 69 ms 460 KB [n = 2000, m = 6100], OK, 6001 operations
47 Correct 70 ms 508 KB [n = 1999, m = 6100], OK, 5998 operations
48 Correct 73 ms 504 KB [n = 1998, m = 6100], OK, 5995 operations
49 Correct 70 ms 504 KB [n = 1997, m = 6100], OK, 5992 operations
50 Correct 70 ms 504 KB [n = 1996, m = 6100], OK, 5989 operations
51 Correct 67 ms 504 KB [n = 2000, m = 6100], OK, 6001 operations
52 Correct 68 ms 632 KB [n = 2000, m = 6100], OK, 6001 operations
53 Correct 1 ms 384 KB [n = 2000, m = 6100], OK: No solution
54 Correct 69 ms 760 KB [n = 2000, m = 6100], OK, 6001 operations
55 Correct 69 ms 504 KB [n = 2000, m = 6100], OK, 6001 operations

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB [n = 1, m = 10000], OK, 4 operations
2 Correct 1 ms 384 KB [n = 2, m = 10000], OK, 7 operations
3 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
4 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
5 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
6 Correct 0 ms 384 KB [n = 8, m = 10000], OK: No solution
7 Correct 0 ms 384 KB [n = 8, m = 10000], OK, 25 operations
8 Correct 1 ms 384 KB [n = 8, m = 10000], OK, 25 operations
9 Correct 1 ms 256 KB [n = 49, m = 10000], OK, 148 operations
10 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
11 Correct 1 ms 384 KB [n = 100, m = 10000], OK, 301 operations
12 Correct 1 ms 384 KB [n = 99, m = 10000], OK, 298 operations
13 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
14 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
15 Correct 1 ms 384 KB [n = 50, m = 10000], OK: No solution
16 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
17 Correct 1 ms 384 KB [n = 50, m = 10000], OK, 151 operations
18 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
19 Correct 19 ms 384 KB [n = 999, m = 10000], OK, 2998 operations
20 Correct 20 ms 384 KB [n = 998, m = 10000], OK, 2995 operations
21 Correct 19 ms 384 KB [n = 997, m = 10000], OK, 2992 operations
22 Correct 20 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
23 Correct 21 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
24 Correct 1 ms 384 KB [n = 1000, m = 10000], OK: No solution
25 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
26 Correct 19 ms 384 KB [n = 1000, m = 10000], OK, 3001 operations
27 Correct 70 ms 452 KB [n = 2000, m = 10000], OK, 6001 operations
28 Correct 69 ms 504 KB [n = 1999, m = 10000], OK, 5998 operations
29 Correct 68 ms 504 KB [n = 1998, m = 10000], OK, 5995 operations
30 Correct 69 ms 504 KB [n = 1997, m = 10000], OK, 5992 operations
31 Correct 68 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
32 Correct 70 ms 524 KB [n = 2000, m = 10000], OK, 6001 operations
33 Correct 1 ms 384 KB [n = 2000, m = 10000], OK: No solution
34 Correct 69 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
35 Correct 70 ms 504 KB [n = 2000, m = 10000], OK, 6001 operations
36 Correct 69 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
37 Correct 70 ms 632 KB [n = 1999, m = 8100], OK, 5998 operations
38 Correct 68 ms 504 KB [n = 1998, m = 8100], OK, 5995 operations
39 Correct 73 ms 504 KB [n = 1997, m = 8100], OK, 5992 operations
40 Correct 69 ms 512 KB [n = 1996, m = 8100], OK, 5989 operations
41 Correct 68 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
42 Correct 70 ms 504 KB [n = 2000, m = 8100], OK, 6001 operations
43 Correct 1 ms 384 KB [n = 2000, m = 8100], OK: No solution
44 Correct 74 ms 436 KB [n = 2000, m = 8100], OK, 6001 operations
45 Correct 69 ms 508 KB [n = 2000, m = 8100], OK, 6001 operations
46 Correct 69 ms 460 KB [n = 2000, m = 6100], OK, 6001 operations
47 Correct 70 ms 508 KB [n = 1999, m = 6100], OK, 5998 operations
48 Correct 73 ms 504 KB [n = 1998, m = 6100], OK, 5995 operations
49 Correct 70 ms 504 KB [n = 1997, m = 6100], OK, 5992 operations
50 Correct 70 ms 504 KB [n = 1996, m = 6100], OK, 5989 operations
51 Correct 67 ms 504 KB [n = 2000, m = 6100], OK, 6001 operations
52 Correct 68 ms 632 KB [n = 2000, m = 6100], OK, 6001 operations
53 Correct 1 ms 384 KB [n = 2000, m = 6100], OK: No solution
54 Correct 69 ms 760 KB [n = 2000, m = 6100], OK, 6001 operations
55 Correct 69 ms 504 KB [n = 2000, m = 6100], OK, 6001 operations
56 Incorrect 68 ms 504 KB Integer 6001 violates the range [-1, 5100]
57 Halted 0 ms 0 KB -