Submission #1115860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115860		Iwantbemaster	Lock Puzzle (innopolis2018_final_A)	C++17	100 / 100	14 ms	760 KiB

A

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define tobit(n) bitset<128>(n)
#define all(v) (v).begin(), (v).end() 
#define rtt(v) rotate(vec.begin(), vec.begin() + k, vec.end()); //move k elements back
int dx[] = {1,0,-1,0,1,1,-1,-1}; int dy[] = {0,1,0,-1,1,-1,1,-1};
const int MOD = 1000000007;
const int MAXN = 2005;
int binpownm(int n, int m){
    if(m <= 1) return n;
    if(m % 2 == 0){
        int t = binpownm(n, m / 2); return t * t;
    } else return binpownm(n, m - 1) * n;
}
string tobin(int n){
    if(n == numeric_limits<int>::min()) return "-1" + string(numeric_limits<int>::digits, '0');
    string res;
    res.reserve(numeric_limits<int>::digits + 1);
    bool cur = (n < 0);
    if(cur) n = -n;
    do { res += char('0' + n % 2); n = n / 2; } while (n > 0);
    if(cur) res += '-';
    return string(res.crbegin(), res.crend());
}
void merge(vector<int>& v, int l, int m, int r){
    vector<int> result; 
    int i = l, j = m + 1;
    while(i <= m && j <= r){
        if(v[i] <= v[j]) result.emplace_back(v[i]), i++;
        else result.emplace_back(v[j]), j++;
    } while(i <= m){
        result.emplace_back(v[i]); i++;
    } while(j <= r){
        result.emplace_back(v[j]); j++; 
    } for(int i = l; i <= r; i++) v[i] = result[i - l];
}
void mergeSORT(vector<int>& v, int l, int r){
    if(l < r){
        int m = (l + r) / 2;
        mergeSORT(v, l, m);
        mergeSORT(v, m + 1, r);
        merge(v, l, m, r);
    }
}
// Алгоритм Манакера || "Короче строка s и мы хотим найти в ней все подпалиндромы" //
vector<int> manacher_odd(string s){ //для нечетных размеров палиндромов
    vector<int> v(s.size(), 1);
    int l = 0, r = 0;
    for(int i = 1; i < s.size(); i++){
        if(i < r) v[i] = min(r - i + 1, v[l + r - i]);
        while(i - v[i] >= 0 && i + v[i] < s.size() && s[i - v[i]] == s[i + v[i]]) v[i]++;
        if(i + v[i] - 1 > r) l = i - v[i] + 1, r = i + v[i] - 1;
    } return v;
}
// Алгоритм Манакера || "Короче строка s и мы хотим найти в ней все подпалиндромы" //
vector<int> manacher_even(string s){ //для четного размеров палиндромов
    vector<int> v(s.size(), 0);
    int l = -1, r = -1;
    for(int i = 0; i < s.size() - 1; i++){
        if(i < r) v[i] = min(r - i, v[l + r - i - 1]);
        while (i - v[i] >= 0 && i + v[i] + 1 < s.size() && s[i - v[i]] == s[i + v[i] + 1]) v[i]++;
        if(i + v[i] > r) l = i - v[i] + 1, r = i + v[i];
    } return v;
}
// PRIMERNO kak pref function no on ishet maksimalnye stroki //
vector<int> z_func(string s){
    vector<int> z(s.size());
    z[0] = 0;
    int l = 0, r = 0;
    for(int i = 1; i < s.size(); i++){
        if(i <= r){
            z[i] = min(z[i - l], r - i + 1);
        }
        while(i + z[i] < s.size() && s[z[i]] == s[i + z[i]]){
            z[i] += 1;
        }
        if(i + z[i] - 1 > r){
            l = i;
            r = i + z[i] - 1;
        }
    } return z;
}
int BIN(vector<int> v, int l, int r, int x){
    if(r >= l){
        int m = l + (r - l) / 2;
        if(v[m] == x) return m;
        if(v[m] > x) return BIN(v, l, m - 1, x);
        return BIN(v, m + 1, r, x);
    } return -1;
}
// PREFIX FUNC p[i] = kolichestvo kakoihto sufix p[i] ravnyy prefu // 
vector<int> p_func(string s){
    vector<int> p(s.size(), 0);
    for(int i = 1; i < s.size(); i++){
        int cur = p[i - 1];
        while(s[i] != s[cur] && cur > 0) cur = p[cur - 1];
        if(s[i] == s[cur]) p[i] = cur + 1;
    } return p;
}
// check to find element in 2D array //
vector<int> FIND2D(vector<vector<int>>& v, int k){
    for(int i = 0; i < v.size(); i++){
        vector<int> cur;
        for(int j = 0; j < v[i].size(); j++){
            cur.emplace_back(v[i][j]);
        }
        int res = BIN(cur, 0, cur.size() - 1, k);
        vector<int> qwe;
        qwe.emplace_back(i);
        qwe.emplace_back(res);
        if(res != -1) return qwe;
    }
    vector<int> qwe = {-1};
    return qwe;
}
int lis(vector<int>& arr) {
    int n = arr.size();
    vector<int> lis(n, 1);
    for(int i = 1; i < n; i++){
        for(int prev = 0; prev < i; prev++){
            if(arr[i] > arr[prev] && lis[i] < lis[prev] + 1){
                lis[i] = lis[prev] + 1;
            }
        }
    } return *max_element(lis.begin(), lis.end());
}
vector<vector<int>> build_prefix_sums_2d(const vector<vector<int>>& a){
    int n = a.size();
    int m = a[0].size();
    vector<vector<int>> prefix_sum(n + 1 , vector<int>(m + 1, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            prefix_sum [i + 1][ j + 1] = prefix_sum[i][j + 1] + prefix_sum[i + 1][j] - prefix_sum[i][j] + a[i][j];
        }
    } return prefix_sum;
}
int findGCD(vector<int> arr, int n){
    int result = arr[0];
    for(int i = 1; i < n; i++) result = __gcd(arr[i], result);
    return result;
}
bool isPrime(int n){
    if(n <= 1) return false;
    if(n <= 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false; 
    for(int i = 5; i * i <= n; i += 6){
        if(n % i == 0 || n % (i + 2) == 0) return false;
    } return true;
}
vector<vector<int>> g; vector<int> vis;
void dfs(int c){
    vis[c] = true;
    for(auto to : g[c]){
        if(vis[to]) continue;
        dfs(to);
    }
}
int n, p[MAXN];
vector<int> ans;
void FUNC(int x){
    x = n - x;
    rotate(p, p + n - x, p + n);
    reverse(p, p + x);
    ans.push_back(x);
}
void solve(){
    int cur = (n / 2) * 2;
    bool rev = 0;
    while(cur >= 2){
        int x, y;
        if(cur == n) x = 0, y = 1;
        else{
            x = p[cur]; y = p[n - 1];
            if(!rev) x--, y++;
            else x++, y--;
        } x = (x + n) % n; y = (y + n) % n;
        int px = find(p, p + n, x) - p;
        FUNC(px + 1); FUNC(0); FUNC(cur);
        int py = find(p, p + n, y) - p; FUNC(py);
        int pxx = find(p, p + n, x) - p; FUNC(pxx + 1);
        rev ^= 1; cur -= 2;
    } if(n > 1){
        int pos = find(p, p + n, 0) - p;
        if(p[(pos + 1) % n] == n - 1) FUNC(0);
        pos = find(p, p + n, 0) - p;
        FUNC(pos); FUNC(n - pos); FUNC(0);
    }
}
signed main(){
    string s, t; int m;
    cin >> n >> m >> s >> t;
    vector<int> r1(n), r2(n);
    iota(r1.begin(), r1.end(), 0); iota(r2.begin(), r2.end(), 0);
    sort(r1.begin(), r1.end(), [&](int x, int y){
        return s[x] < s[y];
    }); //cout << s << endl;
    sort(r2.begin(), r2.end(), [&](int x, int y){
        return t[x] < t[y];
    }); //cout << t << endl;
    // for(auto to : r1) cout << to << " "; cout << endl;
    // for(auto to : r2) cout << to << " "; cout << endl;
    for(int i = 0; i < n; i++){
        if(s[r1[i]] != t[r2[i]]){
            puts("-1");
            return 0;
        }
        p[r1[i]] = r2[i];
    } //for(auto to : p) cout << to << " ";
    solve();
    cout << ans.size() << endl;
    for(auto &i : ans) printf("%d ", i);
}
const int fastIO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    return 0;   
}();

Compilation message (stderr)

A.cpp: In function 'std::vector<long long int> manacher_odd(std::string)':
A.cpp:52:22: 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]
   52 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
A.cpp:54:41: 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]
   54 |         while(i - v[i] >= 0 && i + v[i] < s.size() && s[i - v[i]] == s[i + v[i]]) v[i]++;
      |                                ~~~~~~~~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> manacher_even(std::string)':
A.cpp:62:22: 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]
   62 |     for(int i = 0; i < s.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~
A.cpp:64:46: 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]
   64 |         while (i - v[i] >= 0 && i + v[i] + 1 < s.size() && s[i - v[i]] == s[i + v[i] + 1]) v[i]++;
      |                                 ~~~~~~~~~~~~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> z_func(std::string)':
A.cpp:73:22: 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]
   73 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
A.cpp:77:24: 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]
   77 |         while(i + z[i] < s.size() && s[z[i]] == s[i + z[i]]){
      |               ~~~~~~~~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> p_func(std::string)':
A.cpp:97:22: 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]
   97 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> FIND2D(std::vector<std::vector<long long int> >&, long long int)':
A.cpp:105:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
A.cpp:107:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int j = 0; j < v[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
A.cpp: In function 'int main()':
A.cpp:214:33: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  214 |     for(auto &i : ans) printf("%d ", i);
      |                                ~^    ~
      |                                 |    |
      |                                 int  long long int
      |                                %lld

• Subtask 1: 9 / 9
• Subtask 2: 21 / 21
• Subtask 3: 24 / 24
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11